Level of detail (computer graphics)

Last updated

In computer graphics, level of detail (LOD) refers to the complexity of a 3D model representation. [1] [2] [3] LOD can be decreased as the model moves away from the viewer or according to other metrics such as object importance, viewpoint-relative speed or position. LOD techniques increase the efficiency of rendering by decreasing the workload on graphics pipeline stages, usually vertex transformations. The reduced visual quality of the model is often unnoticed because of the small effect on object appearance when distant or moving fast.

Contents

Although most of the time LOD is applied to geometry detail only, the basic concept can be generalized. Recently, LOD techniques also included shader management to keep control of pixel complexity. A form of level of detail management has been applied to texture maps for years, under the name of mipmapping, also providing higher rendering quality.

It is commonplace to say that "an object has been LOD-ed" when the object is simplified by the underlying LOD-ing algorithm as well as a 3D modeler manually creating LOD models.[ citation needed ]

Historical reference

The origin of all the LOD algorithms for 3D computer graphics can be traced back to an article by James H. Clark in the October 1976 issue of Communications of the ACM . At the time, computers were monolithic and rare, and graphics were being driven by researchers. The hardware itself was completely different, both architecturally and performance-wise. As such, many differences could be observed with regard to today's algorithms but also many common points.

The original algorithm presented a much more generic approach to what will be discussed here. After introducing some available algorithms for geometry management, it is stated that most fruitful gains came from "...structuring the environments being rendered", allowing to exploit faster transformations and clipping operations.

The same environment structuring is now proposed as a way to control varying detail thus avoiding unnecessary computations, yet delivering adequate visual quality:

For example, a dodecahedron looks like a sphere from a sufficiently large distance and thus can be used to model it so long as it is viewed from that or a greater distance. However, if it must ever be viewed more closely, it will look like a dodecahedron. One solution to this is simply to define it with the most detail that will ever be necessary. However, then it might have far more detail than is needed to represent it at large distances, and in a complex environment with many such objects, there would be too many polygons (or other geometric primitives) for the visible surface algorithms to efficiently handle.

The proposed algorithm envisions a tree data structure which encodes in its arcs both transformations and transitions to more detailed objects. In this way, each node encodes an object and according to a fast heuristic, the tree is descended to the leaves which provide each object with more detail. When a leaf is reached, other methods could be used when higher detail is needed, such as Catmull's recursive subdivision .

The significant point, however, is that in a complex environment, the amount of information presented about the various objects in the environment varies according to the fraction of the field of view occupied by those objects.

The paper then introduces clipping (not to be confused with culling although often similar), various considerations on the graphical working set and its impact on performance, interactions between the proposed algorithm and others to improve rendering speed.

Well known approaches

Although the algorithm introduced above covers a whole range of level of detail management techniques, real world applications usually employ specialized methods tailored to the information being rendered. Depending on the requirements of the situation, two main methods are used:

The first method, Discrete Levels of Detail (DLOD), involves creating multiple, discrete versions of the original geometry with decreased levels of geometric detail. At runtime, the full-detail models are substituted for the models with reduced detail as necessary. Due to the discrete nature of the levels, there may be visual popping when one model is exchanged for another. This may be mitigated by alpha blending or morphing between states during the transition.

The second method, Continuous Levels of Detail (CLOD), uses a structure which contains a continuously variable spectrum of geometric detail. The structure can then be probed to smoothly choose the appropriate level of detail required for the situation. A significant advantage of this technique is the ability to locally vary the detail; for instance, the side of a large object nearer to the view may be presented in high detail, while simultaneously reducing the detail on its distant side.

In both cases, LODs are chosen based on some heuristic which is used to judge how much detail is being lost by the reduction in detail, such as by evaluation of the LOD's geometric error relative to the full-detail model. Objects are then displayed with the minimum amount of detail required to satisfy the heuristic, which is designed to minimize geometric detail as much as possible to maximize performance while maintaining an acceptable level of visual quality.

Details on discrete LOD

An example of various DLOD ranges. Darker areas are meant to be rendered with higher detail. An additional culling operation is run, discarding all the information outside the frustum (colored areas). DiscreteLodAndCullExampleRanges.MaxDZ8.svg
An example of various DLOD ranges. Darker areas are meant to be rendered with higher detail. An additional culling operation is run, discarding all the information outside the frustum (colored areas).

The basic concept of discrete LOD (DLOD) is to provide various models to represent the same object. Obtaining those models requires an external algorithm which is often non-trivial and subject of many polygon reduction techniques. Successive LOD-ing algorithms will simply assume those models are available.

DLOD algorithms are often used in performance-intensive applications with small data sets which can easily fit in memory. Although out-of-core algorithms could be used, the information granularity is not well suited to this kind of application. This kind of algorithm is usually easier to get working, providing both faster performance and lower CPU usage because of the few operations involved.

DLOD methods are often used for "stand-alone" moving objects, possibly including complex animation methods. A different approach is used for geomipmapping, a popular terrain rendering algorithm because this applies to terrain meshes which are both graphically and topologically different from "object" meshes. Instead of computing an error and simplify the mesh according to this, geomipmapping takes a fixed reduction method, evaluates the error introduced and computes a distance at which the error is acceptable. Although straightforward, the algorithm provides decent performance.

A discrete LOD example

As a simple example, consider a sphere. A discrete LOD approach would cache a certain number of models to be used at different distances. Because the model can trivially be procedurally generated by its mathematical formulation, using a different number of sample points distributed on the surface is sufficient to generate the various models required. This pass is not a LOD-ing algorithm.

Visual impact comparisons and measurements
Image WireSphereMaxTass.MaxDZ8.jpg WireSphereHiTass.MaxDZ8.jpg WireSphereStdTass.MaxDZ8.jpg WireSphereLowTass.MaxDZ8.jpg WireSphereMinTass.MaxDZ8.jpg
Vertices~5500~2880~1580~670140
NotesMaximum detail,
for closeups
Minimum detail,
very far objects

To simulate a realistic transform bound scenario, an ad-hoc written application can be used. The use of simple algorithms and minimum fragment operations ensures that CPU bounding does not occur. Each frame, the program will compute each sphere's distance and choose a model from a pool according to this information. To easily show the concept, the distance at which each model is used is hard coded in the source. A more involved method would compute adequate models according to the usage distance chosen.

OpenGL is used for rendering due to its high efficiency in managing small batches, storing each model in a display list thus avoiding communication overheads. Additional vertex load is given by applying two directional light sources ideally located infinitely far away.

The following table compares the performance of LOD aware rendering and a full detail (brute force) method.

Visual impact comparisons and measurements
BruteDLODComparison
Rendered
images
SpheresBruteForce.MaxDZ8.jpg SpheresLodded.MaxDZ8.jpg DifferenceImageBruteLod.MaxDZ8.png
Render time27.27 ms1.29 ms21 × reduction
Scene vertices2,328,480109,44021 × reduction

Hierarchical LOD

Because hardware is geared towards large amounts of detail, rendering low polygon objects may score sub-optimal performances. HLOD avoids the problem by grouping different objects together . This allows for higher efficiency as well as taking advantage of proximity considerations.

Practical applications

Video games

LOD is especially useful in 3D video games. Video game developers want to provide players with large worlds but are always constrained by hardware, frame rate and the real-time nature of video game graphics. With the advent of 3D games in the 1990s, a lot of video games simply did not render distant structures or objects. Only nearby objects would be rendered and more distant parts would gradually fade, essentially implementing distance fog. Video games using LOD rendering avoid this fog effect and can render larger areas. Some notable early examples of LOD rendering in 3D video games include The Killing Cloud , Spyro the Dragon , Crash Bandicoot: Warped , Unreal Tournament and the Serious Sam engine. Most modern 3D games use a combination of LOD rendering techniques, using different models for large structures and distance culling for environment details like grass and trees. The effect is sometimes still noticeable, for example when the player character flies over the virtual terrain or uses a sniper scope for long distance viewing. Especially grass and foliage will seem to pop-up when getting closer, also known as foliage culling. [4] LOD can also be used to render fractal terrain in real time. [5] Unreal Engine 5's Nanite system essentially implements level-of-detail within meshes instead of just objects as a whole.

In GIS and 3D city modelling

LOD is found in GIS and 3D city models as a similar concept. It indicates how thoroughly real-world features have been mapped and how much the model adheres to its real-world counterpart. Besides the geometric complexity, other metrics such as spatio-semantic coherence, resolution of the texture and attributes can be considered in the LOD of a model. The standard CityGML contains one of the most prominent LOD categorizations.

The analogy of "LOD-ing" in GIS is referred to as generalization.

Rendering and modeling software

See also

Related Research Articles

<span class="mw-page-title-main">Rendering (computer graphics)</span> Process of generating an image from a model

Rendering or image synthesis is the process of generating a photorealistic or non-photorealistic image from a 2D or 3D model by means of a computer program. The resulting image is referred to as a rendering. Multiple models can be defined in a scene file containing objects in a strictly defined language or data structure. The scene file contains geometry, viewpoint, textures, lighting, and shading information describing the virtual scene. The data contained in the scene file is then passed to a rendering program to be processed and output to a digital image or raster graphics image file. The term "rendering" is analogous to the concept of an artist's impression of a scene. The term "rendering" is also used to describe the process of calculating effects in a video editing program to produce the final video output.

<span class="mw-page-title-main">Texture mapping</span> Method of defining surface detail on a computer-generated graphic or 3D model

Texture mapping is a method for mapping a texture on a computer-generated graphic. "Texture" in this context can be high frequency detail, surface texture, or color.

<span class="mw-page-title-main">Point cloud</span> Set of data points in three-dimensional space

A point cloud is a discrete set of data points in space. The points may represent a 3D shape or object. Each point position has its set of Cartesian coordinates. Points may contain data other than position such as RGB colors, normals, timestamps and others. Point clouds are generally produced by 3D scanners or by photogrammetry software, which measure many points on the external surfaces of objects around them. As the output of 3D scanning processes, point clouds are used for many purposes, including to create 3D computer-aided design (CAD) or geographic information systems (GIS) models for manufactured parts, for metrology and quality inspection, and for a multitude of visualizing, animating, rendering, and mass customization applications.

<span class="mw-page-title-main">Shading</span> Depicting depth through varying levels of darkness

Shading refers to the depiction of depth perception in 3D models or illustrations by varying the level of darkness. Shading tries to approximate local behavior of light on the object's surface and is not to be confused with techniques of adding shadows, such as shadow mapping or shadow volumes, which fall under global behavior of light.

<span class="mw-page-title-main">Volume rendering</span> Representing a 3D-modeled object or dataset as a 2D projection

In scientific visualization and computer graphics, volume rendering is a set of techniques used to display a 2D projection of a 3D discretely sampled data set, typically a 3D scalar field.

<span class="mw-page-title-main">Polygon mesh</span> Set of polygons to define a 3D model

In 3D computer graphics and solid modeling, a polygon mesh is a collection of vertices, edges and faces that defines the shape of a polyhedral object. The faces usually consist of triangles, quadrilaterals (quads), or other simple convex polygons (n-gons), since this simplifies rendering, but may also be more generally composed of concave polygons, or even polygons with holes.

Real-time optimally adapting mesh (ROAM) is a continuous level of detail algorithm that optimizes terrain meshes. On modern computers, sometimes it is more effective to send a small amount of unneeded polygons to the GPU, rather than burden the CPU with LOD calculations—making algorithms like geomipmapping more effective than ROAM. This technique is used by graphics programmers in order to produce high quality displays while being able to maintain real-time frame rates. Algorithms such as ROAM exist to provide a control over scene quality versus performance in order to provide HQ scenes while retaining real-time frame rates on hardware. ROAM largely aims toward terrain visualization, but various elements from ROAM are difficult to place within a game system.

<span class="mw-page-title-main">Low poly</span> 3D computer graphics mesh with low number of polygons

Low poly is a polygon mesh in 3D computer graphics that has a relatively small number of polygons. Low poly meshes occur in real-time applications as contrast with high-poly meshes in animated movies and special effects of the same era. The term low poly is used in both a technical and a descriptive sense; the number of polygons in a mesh is an important factor to optimize for performance but can give an undesirable appearance to the resulting graphics.

<span class="mw-page-title-main">Polygonal modeling</span> Object modeling method

In 3D computer graphics, polygonal modeling is an approach for modeling objects by representing or approximating their surfaces using polygon meshes. Polygonal modeling is well suited to scanline rendering and is therefore the method of choice for real-time computer graphics. Alternate methods of representing 3D objects include NURBS surfaces, subdivision surfaces, and equation-based representations used in ray tracers.

Clipping, in the context of computer graphics, is a method to selectively enable or disable rendering operations within a defined region of interest. Mathematically, clipping can be described using the terminology of constructive geometry. A rendering algorithm only draws pixels in the intersection between the clip region and the scene model. Lines and surfaces outside the view volume are removed.

<span class="mw-page-title-main">Heightmap</span> Type of raster image in computer graphics

In computer graphics, a heightmap or heightfield is a raster image used mainly as Discrete Global Grid in secondary elevation modeling. Each pixel stores values, such as surface elevation data, for display in 3D computer graphics. A heightmap can be used in bump mapping to calculate where this 3D data would create shadow in a material, in displacement mapping to displace the actual geometric position of points over the textured surface, or for terrain where the heightmap is converted into a 3D mesh.

<span class="mw-page-title-main">3D rendering</span> Process of converting 3D scenes into 2D images

3D rendering is the 3D computer graphics process of converting 3D models into 2D images on a computer. 3D renders may include photorealistic effects or non-photorealistic styles.

Computer graphics lighting is the collection of techniques used to simulate light in computer graphics scenes. While lighting techniques offer flexibility in the level of detail and functionality available, they also operate at different levels of computational demand and complexity. Graphics artists can choose from a variety of light sources, models, shading techniques, and effects to suit the needs of each application.

<span class="mw-page-title-main">3D computer graphics</span> Graphics that use a three-dimensional representation of geometric data

3D computer graphics, sometimes called CGI, 3-D-CGI or three-dimensional computer graphics, are graphics that use a three-dimensional representation of geometric data that is stored in the computer for the purposes of performing calculations and rendering digital images, usually 2D images but sometimes 3D images. The resulting images may be stored for viewing later or displayed in real time.

<span class="mw-page-title-main">Computer graphics (computer science)</span> Sub-field of computer science

Computer graphics is a sub-field of computer science which studies methods for digitally synthesizing and manipulating visual content. Although the term often refers to the study of three-dimensional computer graphics, it also encompasses two-dimensional graphics and image processing.

<span class="mw-page-title-main">3D modeling</span> Form of computer-aided engineering

In 3D computer graphics, 3D modeling is the process of developing a mathematical coordinate-based representation of a surface of an object in three dimensions via specialized software by manipulating edges, vertices, and polygons in a simulated 3D space.

<span class="mw-page-title-main">Popping (computer graphics)</span> Undesirable visual effect in 3D computer graphics

In 3D computer graphics, popping refers to an undesirable visual effect that occurs when the transition of a 3D object to a different pre-calculated level of detail (LOD) is abrupt and obvious to the viewer. The LOD-ing algorithm reduces the geometrical complexity of a 3D object the further it is from the viewer and returns that lost complexity as the viewer gets closer to the 3D object, causing it to pop as it becomes suddenly more detailed. The LOD-ing algorithms can depend on more factors than just distance from the viewer, but it is often the primary factor that is considered. Popping is most obvious when switching between different LODs directly without intermediate steps. Techniques like geomorphing and LOD blending can reduce visual popping significantly by making the transitions more gradual.

<span class="mw-page-title-main">Tessellation (computer graphics)</span> Computer graphics terminology

In computer graphics, tessellation is the dividing of datasets of polygons presenting objects in a scene into suitable structures for rendering. Especially for real-time rendering, data is tessellated into triangles, for example in OpenGL 4.0 and Direct3D 11.

This is a glossary of terms relating to computer graphics.

<span class="mw-page-title-main">Amitabh Varshney</span> American computer scientist

Amitabh Varshney is an Indian-born American computer scientist. He is an IEEE fellow, and serves as Dean of the University of Maryland College of Computer, Mathematical, and Natural Sciences. Before being named Dean, Varshney was the director of the University of Maryland Institute for Advanced Computer Studies (UMIACS) from 2010 to 2018.

References

  1. "Multiple levels of detail" (PDF). clemson.edu. Retrieved 2 July 2023.
  2. "Levels of Detail LOD" (PDF). computer-graphics.se. Retrieved 2 July 2023.
  3. "GPU based dynamic geometry LOD – RasterGrid".
  4. "Foliage Mode". docs.unrealengine.com. Retrieved 2 July 2023.
  5. "Musgrave, F. Kenton, Craig E. Kolb, and Robert S. Mace. "The synthesis and rendering of eroded fractal terrains." ACM Siggraph Computer Graphics. Vol. 23. No. 3. ACM, 1989" (PDF). Retrieved 2 July 2023.
  1. ^ Communications of the ACM, October 1976 Volume 19 Number 10. Pages 547–554. Hierarchical Geometric Models for Visible Surface Algorithms by James H. Clark, University of California at Santa Cruz. Digitalized scan is freely available at https://web.archive.org/web/20060910212907/http://accad.osu.edu/%7Ewaynec/history/PDFs/clark-vis-surface.pdf.
  2. ^ Catmull E., A Subdivision Algorithm for Computer Display of Curved Surfaces. Tech. Rep. UTEC-CSc-74-133, University of Utah, Salt Lake City, Utah, Dec. 1
  3. ^ Ribelles, López, and Belmonte, "An Improved Discrete Level of Detail Model Through an Incremental Representation", 2010, Available at http://www3.uji.es/~ribelles/papers/2010-TPCG/tpcg10.pdf
  4. ^ de Boer, W.H., Fast Terrain Rendering using Geometrical Mipmapping, in flipCode featured articles, October 2000. Available at flipcode - Fast Terrain Rendering Using Geometrical MipMapping.
  5. ^ Carl Erikson's paper at http://www.cs.unc.edu/Research/ProjectSummaries/hlods.pdf provides a quick, yet effective overlook at HLOD mechanisms. A more involved description follows in his thesis, at https://wwwx.cs.unc.edu/~geom/papers/documents/dissertations/erikson00.pdf.