Level of detail (computer graphics)
   HOME

TheInfoList



OR:

In
computer graphics Computer graphics deals with generating images with the aid of computers. Today, computer graphics is a core technology in digital photography, film, video games, cell phone and computer displays, and many specialized applications. A great de ...
, level of detail (LOD) refers to the complexity of a
3D model In 3D computer graphics, 3D modeling is the process of developing a mathematical coordinate-based representation of any surface of an object (inanimate or living) in three dimensions via specialized software by manipulating edges, vertices, an ...
representation. 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 In computer graphics, a computer graphics pipeline, rendering pipeline or simply graphics pipeline, is a conceptual model that describes what steps a graphics system needs to perform to Rendering (computer graphics), render a ...
stages, usually
vertex transformations In linear algebra, linear transformations can be represented by matrices. If T is a linear transformation mapping \mathbb^n to \mathbb^m and \mathbf x is a column vector with n entries, then T( \mathbf x ) = A \mathbf x for some m \times n matrix ...
. The reduced visual quality of the model is often unnoticed because of the small effect on object appearance when distant or moving fast. Although most of the time LOD is applied to geometry detail only, the basic concept can be generalized. Recently, LOD techniques also included
shader In computer graphics, a shader is a computer program that calculates the appropriate levels of light, darkness, and color during the rendering of a 3D scene - a process known as ''shading''. Shaders have evolved to perform a variety of spec ...
management to keep control of pixel complexity. A form of level of detail management has been applied to
texture map Texture mapping is a method for mapping a texture on a computer-generated graphic. Texture here can be high frequency detail, surface texture, or color. History The original technique was pioneered by Edwin Catmull in 1974. Texture mapping ...
s for years, under the name of
mipmapping In computer graphics, mipmaps (also MIP maps) or pyramids are pre-calculated, optimized sequences of images, each of which is a progressively lower resolution representation of the previous. The height and width of each image, or level, in the ...
, 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..


Historical reference

The origin of all the LOD algorithms for 3D computer graphics can be traced back to an article by
James H. Clark James Henry Clark (born March 23, 1944) is an American entrepreneur and computer scientist. He founded several notable Silicon Valley technology companies, including Silicon Graphics, Netscape, myCFO, and Healtheon. His research work in comput ...
in the October 1976 issue of ''
Communications of the ACM ''Communications of the ACM'' is the monthly journal of the Association for Computing Machinery (ACM). It was established in 1958, with Saul Rosen as its first managing editor. It is sent to all ACM members. Articles are intended for readers with ...
''. 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 Clipping may refer to: Words * Clipping (morphology), the formation of a new word by shortening it, e.g. "ad" from "advertisement" * Clipping (phonetics), shortening the articulation of a speech sound, usually a vowel * Clipping (publications) ...
operations. The same environment structuring is now proposed as a way to control varying detail thus avoiding unnecessary computations, yet delivering adequate visual quality: The proposed algorithm envisions a
tree data structure In computer science, a tree is a widely used abstract data type that represents a hierarchical tree structure with a set of connected nodes. Each node in the tree can be connected to many children (depending on the type of tree), but must be conn ...
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 A heuristic (; ), or heuristic technique, is any approach to problem solving or self-discovery that employs a practical method that is not guaranteed to be optimal, perfect, or rational, but is nevertheless sufficient for reaching an immediate, ...
, 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 This is a glossary of terms relating to computer graphics Computer graphics deals with generating images with the aid of computers. Today, computer graphics is a core technology in digital photography, film, video games, cell phone and comp ...
. The paper then introduces
clipping Clipping may refer to: Words * Clipping (morphology), the formation of a new word by shortening it, e.g. "ad" from "advertisement" * Clipping (phonetics), shortening the articulation of a speech sound, usually a vowel * Clipping (publications) ...
(not to be confused with
culling In biology, culling is the process of segregating organisms from a group according to desired or undesired characteristics. In animal breeding, it is the process of removing or segregating animals from a breeding stock based on a specific tr ...
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 Popping is a street dance adapted out of the earlier Boogaloo (funk dance) cultural movement in Oakland, California. As Boogaloo spread, it would be referred to as Robottin in Richmond, California, Strutting movements in San Francisco and San ...
when one model is exchanged for another. This may be mitigated by
alpha blending In computer graphics, alpha compositing or alpha blending is the process of combining one image with a background to create the appearance of partial or full transparency. It is often useful to render picture elements (pixels) in separate pas ...
or
morphing Morphing is a special effect in motion pictures and animations that changes (or morphs) one image or shape into another through a seamless transition. Traditionally such a depiction would be achieved through dissolving techniques on film. Since ...
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

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 technique In geometry, a polygon () is a plane figure that is described by a finite number of straight line segments connected to form a closed ''polygonal chain'' (or ''polygonal circuit''). The bounded plane region, the bounding circuit, or the two to ...
s. 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 In computing, external memory algorithms or out-of-core algorithms are algorithms that are designed to process data that are too large to fit into a computer's main memory at once. Such algorithms must be optimized to efficiently fetch and access d ...
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 Geomipmapping or geometrical mipmapping is a real-time block-based terrain rendering algorithm developed by W.H. de Boer in 2000 that aims to reduce CPU processing time which is a common bottleneck in level of detail approaches to terrain render ...
, a popular
terrain rendering Terrain cartography or relief mapping is the depiction of the shape of the surface of the Earth on a map, using one or more of several techniques that have been developed. Terrain or relief is an essential aspect of physical geography, and as su ...
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 sphere () is a Geometry, geometrical object that is a solid geometry, three-dimensional analogue to a two-dimensional circle. A sphere is the Locus (mathematics), set of points that are all at the same distance from a given point in three ...
. 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 In computing, procedural generation is a method of creating data algorithmically as opposed to manually, typically through a combination of human-generated assets and algorithms coupled with computer-generated randomness and processing power. In ...
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. 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 bound {{Unreferenced, date=April 2007 In computer science, a computer is CPU-bound (or compute-bound) when the time for it to complete a task is determined principally by the speed of the central processor: processor utilization is high, perhaps at 100% ...
ing 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 OpenGL (Open Graphics Library) is a cross-language, cross-platform application programming interface (API) for rendering 2D and 3D vector graphics. The API is typically used to interact with a graphics processing unit (GPU), to achieve hardwa ...
is used for rendering due to its high efficiency in managing small batches, storing each model in a
display list A display list (or ''display file'') is a series of graphics commands that define an output image. The image is created ( ''rendered'') by executing the commands to combine various primitives. This activity is most often performed by specialized di ...
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.


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 Real-time or real time describes various operations in computing or other processes that must guarantee response times within a specified time (deadline), usually a relatively short time. A real-time process is generally one that happens in defined ...
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 Distance fog is a technique used in 3D computer graphics to enhance the perception of distance by shading distant objects differently. Because many of the shapes in graphical environments are relatively simple, and complex shadows are difficult ...
. 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 ''Spyro the Dragon'' is a platform game developed by Insomniac Games and published by Sony Computer Entertainment for the PlayStation on September 9, 1998. The first game in the ''Spyro'' series, it stars the title character, a young purple dr ...
'', '' Crash Bandicoot: Warped'', ''
Unreal Tournament ''Unreal Tournament'' is a first-person arena shooter video game developed by Epic Games and Digital Extremes. The second installment in the '' Unreal'' series, it was first published by GT Interactive in 1999 for Microsoft Windows, and late ...
'' and the ''
Serious Sam ''Serious Sam'' is a video game series created and primarily developed by Croteam. It consists predominantly of first-person shooters. The series follows the advances of mercenary Sam "Serious" Stone against Mental, an extraterrestrial overl ...
'' 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. LOD can also be used to render
fractal terrain A fractal landscape is a surface that is generated using a stochastic algorithm designed to produce fractal behavior that mimics the appearance of natural terrain. In other words, the result of the procedure is not a deterministic fractal surface, ...
in real time.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.
/ref>
Unreal Engine 5 Unreal Engine (UE) is a 3D computer graphics game engine developed by Epic Games, first showcased in the 1998 first-person shooter game ''Unreal''. Initially developed for PC first-person shooters, it has since been used in a variety of genr ...
's ''Nanite'' system essentially implements level-of-detail within meshes instead of just objects as a whole. In the popular city building game '' Cities: Skylines'', mods allow various degrees of LOD-ing.


In GIS and 3D city modelling

LOD is found in
GIS A geographic information system (GIS) is a type of database containing Geographic data and information, geographic data (that is, descriptions of phenomena for which location is relevant), combined with Geographic information system software, sof ...
and
3D city models A 3D city model is digital model of urban areas that represent terrain surfaces, sites, buildings, vegetation, infrastructure and landscape elements in three-dimensional scale as well as related objects (e.g., city furniture) belonging to urban a ...
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 CityGML is an open standardised data model and exchange format to store digital 3D models of cities and landscapes. It defines ways to describe most of the common 3D features and objects found in cities (such as buildings, roads, rivers, bridges, ...
contains one of the most prominent LOD categorizations. The analogy of "LOD-ing" in GIS is referred to as
generalization A generalization is a form of abstraction whereby common properties of specific instances are formulated as general concepts or claims. Generalizations posit the existence of a domain or set of elements, as well as one or more common characteri ...
.


Rendering and modeling software

*
MeshLab MeshLab is a 3D mesh processing software system that is oriented to the management and processing of unstructured large meshes and provides a set of tools for editing, cleaning, healing, inspecting, rendering, and converting these kinds of meshes ...
an open source mesh processing tool that is able to accurately simplify 3D polygonal meshes. * Polygon Cruncher a commercial software from Mootools that reduces the number of polygons of objects without changing their appearance. *
Simplygon Simplygon is 3D computer graphics software for automatic 3D optimization, based on proprietary methods for creating levels of detail (LODs) through Polygon mesh reduction and other optimization techniques. Since the launch of Simplygon, the pro ...
a commercial mesh processing package for remeshing general input meshes into
real-time Real-time or real time describes various operations in computing or other processes that must guarantee response times within a specified time (deadline), usually a relatively short time. A real-time process is generally one that happens in defined ...
renderable meshes.


See also

* Progressive refinement * Progressive meshes *
Sparse voxel octree A sparse voxel octree (SVO) is a 3D computer graphics rendering technique using a raycasting or sometimes a ray tracing approach into an octree data representation. The technique generally relies on generating and processing the hull of points ( ...
*
Spatial resolution In physics and geosciences, the term spatial resolution refers to distance between independent measurements, or the physical dimension that represents a pixel of the image. While in some instruments, like cameras and telescopes, spatial resolutio ...


References

# Communications of the ACM, October 1976 Volume 19 Number 10. Pages 547–554. ''Hierarchical Geometric Models for Visible Surface Algorithms'' by
James H. Clark James Henry Clark (born March 23, 1944) is an American entrepreneur and computer scientist. He founded several notable Silicon Valley technology companies, including Silicon Graphics, Netscape, myCFO, and Healtheon. His research work in comput ...
, 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. # 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 # 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 # de Boer, W.H., ''Fast Terrain Rendering using Geometrical Mipmapping'', in flipCode featured articles, October 2000. Available at https://www.flipcode.com/archives/Fast_Terrain_Rendering_Using_Geometrical_MipMapping.shtml. # 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. {{DEFAULTSORT:Level Of Detail 3D rendering