HOME

TheInfoList




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 dea ...

computer graphics
, level of detail (LOD) refers to the complexity of a
3D model
3D model
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. 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 Computer graphics deals with generating images with the aid of computers A computer is a machine that can be programmed to Execution (computing), carry out sequences of arithmetic or logical operations automatic ...
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 defining high frequency detail Detail(s) or The Detail(s) may refer to: Film and television * ''Details'' (film), a 2003 Swedish film * ''The Details'' (film), a 2011 American film * ''The Detail ''The Deta ...
s for years, under the name of
mipmapping 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 a ...
, 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''.


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 H. Clark
in the October 1976 issue of ''
Communications of the ACM ''Communications of the ACM'' is the monthly journal A journal, from the Old French ''journal'' (meaning "daily"), may refer to: *Bullet journal, a method of personal organizations *Diary, a record of what happened over the course of a day or ot ...
''. 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) In linguistics Linguistics is the scientific study of language A language is a structured system of communication Communication (from Latin Latin (, or , ) is a cla ...
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 Computer science deals with the theoretical foundations of information, algorithms and the architectures of its computation as well as practical techniques for their application. Computer science is the study of , ...
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 Mathematical optimisation, optimal, perfect, or Rationality, rational, but is nevertheless ...
, 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 compu ...
. The paper then introduces
clipping Clipping may refer to: Words * Clipping (morphology) In linguistics Linguistics is the scientific study of language A language is a structured system of communication Communication (from Latin Latin (, or , ) is a cla ...
(not to be confused with
culling In biology Biology is the natural science that studies life and living organisms, including their anatomy, physical structure, Biochemistry, chemical processes, Molecular biology, molecular interactions, Physiology, physiological mechan ...
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), Boogaloo cultural movement in Oakland, California, Oakland, California. As Boogaloo (funk dance), Boogaloo spread, it would be referred to as Robottin in Richmond, Cali ...
when one model is exchanged for another. This may be mitigated by
alpha blending 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 ...
or
morphing Morphing is a special effect Special effects (often abbreviated as SFX, SPFX, F/X or simply FX) are illusions or visual tricks used in the theatre, film, television, video game A video game is an electronic game that involves interact ...
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 Geometry (from the grc, γεωμετρία; ' "earth", ' "measurement") is, with , one of the oldest branches of . It is concerned with properties of space that are related with distance, shape, size, and relative position o ...
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 Computing is any goal-oriented activity requiring, benefiting from, or creating computing machinery. It includes the study and experimentation of algorithmic processes and development of both computer hardware , hardware and softwar ...
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 A central processing unit (CPU), also called a central processor, main processor or just processor, is the electronic circuit File:PExdcr01CJC.jpg, 200px, A circuit built on a printed circuit board (PCB). An electronic circuit is composed of ...

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 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 ...
, 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 ...

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 sphere (from Greek#REDIRECT Greek Greek may refer to: Greece Anything of, from, or related to Greece Greece ( el, Ελλάδα, , ), officially the Hellenic Republic, is a country located in Southeast Europe. Its population is appr ...

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 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 Computer science deals with the theoretical foundations of information, algorithms and the architectures of its computation as well as practical techniques for their application. Compu ...
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 Hard coding (also hard-coding or hardcoding) is the software development practice of embedding data directly into the source code of a computer program, program or other executable object, as opposed to obtaining the data from external sources or g ...
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 In computing Computing is any goal-oriented activity requiring, benefiting from, or creating computing machinery. It includes the study and experimentation of algorithm ...
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 3D computer graphics, sometimes called CGI, 3DCG or three-dimensional computer graphics (in contrast to 2D computer graphics 2D computer graphics is the Computer-generated imagery, comp ...
. 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 (console), PlayStation on September 9, 1998. The first game in the ''Spyro'' series, it stars the title chara ...
'', '' Crash Bandicoot: Warped'', ''
Unreal Tournament ''Unreal Tournament'' is a first-person shooter, first-person arena shooter video game developed by Epic Games and Digital Extremes. The second installment in the ''Unreal (video game series), Unreal'' series, it was first published by Atari, ...
'' and the ''
Serious Sam ''Serious Sam'' is a video game series This is a list of video game franchises, organized alphabetically. All entries include multiple video games, not counting ports or altered re-releases. 0–9 *''1080° Snowboarding is a 1998 sno ...

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. LOD can also be used to render
fractal terrain
fractal terrain
in real time. Unreal Engine 5'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 ''Cities: Skylines'' is a 2015 city-building game developed by Colossal Order (company), Colossal Order and published by Paradox Interactive. The game is a single-player open-ended city-building game, city-building simulation. Players engage in ...
, 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 In computing Computing is any goal-oriented activity requiring, benefiting from, or creating computing machinery. It includes the study and experimentation of algorithmic processe ...

GIS
and
3D city models A 3D city model is 3D modeling, 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) belongin ...
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 city models, 3D models of cities and Digital elevation model, landscapes. It defines ways to describe most of the common 3D features and objects found in cities (suc ...
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 Abstraction in its main sense is a conceptual process where general rules Rule or ruling may refer to: Human activity * The exercise of political Politics (from , ) is the set of activities ...
.


Rendering and modeling software

*
MeshLab MeshLab is a 3D geometry processing, 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 t ...
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 a commercial mesh processing package for
remeshing
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 (graphics), ray tracing approach into an octree data representation. The technique generally relies on generating and processi ...
*
Spatial resolution In physics Physics is the natural science that studies matter, its Elementary particle, fundamental constituents, its Motion (physics), motion and behavior through Spacetime, space and time, and the related entities of energy and force. "P ...


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 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. # 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