Voxel

Last updated
A series of voxels in a stack, with a single voxel shaded Voxels.svg
A series of voxels in a stack, with a single voxel shaded
Illustration of a voxel grid containing color values Voxelgitter.png
Illustration of a voxel grid containing color values

In 3D computer graphics, a voxel represents a value on a regular grid in three-dimensional space. As with pixels in a 2D bitmap, voxels themselves do not typically have their position (i.e. coordinates) explicitly encoded with their values. Instead, rendering systems infer the position of a voxel based upon its position relative to other voxels (i.e., its position in the data structure that makes up a single volumetric image).

Contents

In contrast to pixels and voxels, polygons are often explicitly represented by the coordinates of their vertices (as points). A direct consequence of this difference is that polygons can efficiently represent simple 3D structures with much empty or homogeneously filled space, while voxels excel at representing regularly sampled spaces that are non-homogeneously filled.

Voxels are frequently used in the visualization and analysis of medical and scientific data (e.g. geographic information systems (GIS)). [1] Some volumetric displays use voxels to describe their resolution. For example, a cubic volumetric display might be able to show 512×512×512 (or about 134 million) voxels.

One of the definitions is:

Voxel is an image of a three-dimensional space region limited by given sizes, which has its own nodal point coordinates in an accepted coordinate system, its own form, its own state parameter that indicates its belonging to some modeled object, and has properties of modeled region.

This definition has the following advantage. If fixed voxel form is used within the whole model it is much easier to operate with voxel nodal points (i.e. three coordinates of this point). Yet, there is the simple form of record: indexes of the elements in the model set (i.e. integer coordinates). Model set elements in this case are state parameters, indicating voxel belonging to the modeled object or its separate parts, including their surfaces. [2]

Etymology

The word voxel originated by analogy to "pixel", with vo representing "volume" (instead of pixel's "picture") and el representing "element"; [3] a similar formation with el for "element" is the word "texel". [3] The term hypervoxel is a generalization of voxel for higher-dimensional spaces.

Rendering

A volume described as voxels can be visualized either by direct volume rendering or by the extraction of polygon iso-surfaces that follow the contours of given threshold values. The marching cubes algorithm is often used for isosurface extraction, however other methods exist as well.

Both ray tracing and ray casting, as well as rasterisation, can be applied to voxel data to obtain 2D raster graphics to depict on a monitor.

Incremental error rasterisation

Another technique for voxels involves raster graphics where one simply raytraces every pixel of the display into the scene, tracking an error term to determine when to step. A typical implementation will raytrace each pixel of the display starting at the bottom of the screen using what is known as a y-buffer. When a voxel is reached that has a higher y value on the display it is added to the y-buffer overriding the previous value and connected with the previous y-value on the screen interpolating the color values. There is a major downside to voxel rasterization when transformation is applied which causes severe aliasing. The advantage was the ability to rasterise using cheap integer calculations on a CPU without hardware acceleration. [4]

Outcast , and other 1990s video games employed this graphics technique for effects such as reflection and bump-mapping and usually for terrain rendering. Outcast's graphics engine was mainly a combination of a ray casting (heightmap) engine, used to render the landscape, and a texture mapping polygon engine used to render objects. The "Engine Programming" section of the games credits in the manual has several subsections related to graphics, among them: "Landscape Engine", "Polygon Engine", "Water & Shadows Engine" and "Special effects Engine". [5] Although Outcast is often cited as a forerunner of voxel technology, [6] this is somewhat misleading. The game does not actually model three-dimensional volumes of voxels. Instead, it models the ground as a surface, which may be seen as being made up of voxels. The ground is decorated with objects that are modeled using texture-mapped polygons. When Outcast was developed, the term "voxel engine", when applied to computer games, commonly referred to a ray casting engine (for example the VoxelSpace engine). On the engine technology page of the game's website, the landscape engine is also referred to as the "Voxels engine". [7] The engine is purely software-based; it does not rely on hardware-acceleration via a 3D graphics card. [8]

John Carmack also experimented with Voxels for the Quake III engine. [9] One such problem cited by Carmack was the lack of graphics cards designed specifically for such rendering requiring them to be software rendered.

Comanche was also the first commercial flight simulation based on voxel technology. NovaLogic used the proprietary Voxel Space engine developed for the company by Kyle Freeman [10] (written entirely in Assembly language) to create open landscapes. [11] This rendering technique allowed for much more detailed and realistic terrain compared to simulations based on vector graphics at that time. [8]

Data

A voxel represents a single sample, or data point, on a regularly spaced, three-dimensional grid. This data point can consist of a single piece of data, such as an opacity, or multiple pieces of data, such as a color in addition to opacity. A voxel represents only a single point on this grid, not a volume; the space between each voxel is not represented in a voxel-based dataset. Depending on the type of data and the intended use for the dataset, this missing information may be reconstructed and/or approximated, e.g. via interpolation.

In computed tomography (abdominal CT pictured), voxels are generated by multiplying the field of view (FOV) by the scan range. Abdominal CT with scan range and field of view, with box and text.jpg
In computed tomography (abdominal CT pictured), voxels are generated by multiplying the field of view (FOV) by the scan range.

The value of a voxel may represent various properties. In CT scans, the values are Hounsfield units, giving the opacity of material to X-rays. [12] : 29  Different types of value are acquired from MRI or ultrasound.

Voxels can contain multiple scalar values, essentially vector (tensor) data; in the case of ultrasound scans with B-mode and Doppler data, density, and volumetric flow rate are captured as separate channels of data relating to the same voxel positions.

While voxels provide the benefit of precision and depth of reality, they are typically large data sets and are unwieldy to manage given the bandwidth of common computers. However, through efficient compression and manipulation of large data files, interactive visualization can be enabled on consumer market computers.

Other values may be useful for immediate 3D rendering, such as a surface normal vector and color.

Technologies to extend voxels into 4 and 5 dimensions of data are under investigation. [13]

Uses

Common uses of voxels include volumetric imaging in medicine and representation of terrain in games and simulations. Voxel terrain is used instead of a heightmap because of its ability to represent overhangs, caves, arches, and other 3D terrain features. These concave features cannot be represented in a heightmap due to only the top 'layer' of data being represented, leaving everything below it filled (the volume that would otherwise be the inside of the caves, or the underside of arches or overhangs).

Computer games

Editors

While scientific volume visualization does not require modifying the actual voxel data, voxel editors can be used to create art (especially 3D pixel art) and models for voxel based games. Some editors are focused on a single approach to voxel editing while others mix various approaches. Some common approaches are:

There are a few voxel editors available that are not tied to specific games or engines. They can be used as alternatives or complements to traditional 3D vector modeling.

Extensions

A generalization of a voxel is the toxel, or temporal voxel. [24] This is used in the case of a 4D dataset, for example, an image sequence that represents 3D space together with another dimension such as time. In this way, an image could contain 100×100×100×100 toxels, which could be seen as a series of 100 frames of a 100×100×100 volume image (the equivalent for a 3D image would be showing a 2D cross section of the image in each frame). Although storage and manipulation of such data requires large amounts of memory, it allows the representation and analysis of spacetime systems.

See also

Related Research Articles

<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 here can be high frequency detail, surface texture, or color.

<span class="mw-page-title-main">Ray casting</span> Methodological basis for 3D CAD/CAM solid modeling and image rendering

Ray casting is the methodological basis for 3D CAD/CAM solid modeling and image rendering. It is essentially the same as ray tracing for computer graphics where virtual light rays are "cast" or "traced" on their path from the focal point of a camera through each pixel in the camera sensor to determine what is visible along the ray in the 3D scene. The term "Ray Casting" was introduced by Scott Roth while at the General Motors Research Labs from 1978–1980. His paper, "Ray Casting for Modeling Solids", describes modeled solid objects by combining primitive solids, such as blocks and cylinders, using the set operators union (+), intersection (&), and difference (-). The general idea of using these binary operators for solid modeling is largely due to Voelcker and Requicha's geometric modelling group at the University of Rochester. See solid modeling for a broad overview of solid modeling methods. This figure on the right shows a U-Joint modeled from cylinders and blocks in a binary tree using Roth's ray casting system in 1979.

<span class="mw-page-title-main">Scientific visualization</span> Interdisciplinary branch of science concerned with presenting scientific data visually

Scientific visualization is an interdisciplinary branch of science concerned with the visualization of scientific phenomena. It is also considered a subset of computer graphics, a branch of computer science. The purpose of scientific visualization is to graphically illustrate scientific data to enable scientists to understand, illustrate, and glean insight from their data. Research into how people read and misread various types of visualizations is helping to determine what types and features of visualizations are most understandable and effective in conveying information.

<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">Isosurface</span> Surface representing points of constant value within a volume

An isosurface is a three-dimensional analog of an isoline. It is a surface that represents points of a constant value within a volume of space; in other words, it is a level set of a continuous function whose domain is 3-space.

A first-person shooter engine is a video game engine specialized for simulating 3D environments for use in a first-person shooter video game. First-person refers to the view where the players see the world from the eyes of their characters. Shooter refers to games which revolve primarily around wielding firearms and killing other entities in the game world, either non-player characters or other players.

In computer graphics, level of detail (LOD) refers to the complexity of a 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 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.

<i>Quake</i> engine Video game engine developed by id Software

The Quake engine is the game engine developed by id Software to power their 1996 video game Quake. It featured true 3D real-time rendering and since 2012, licensed under the terms of GNU General Public License v2.0 or later.

<i>Outcast</i> (video game) 1999 video game

Outcast is an action-adventure game developed by Appeal and released by Infogrames for Windows in 1999. The game was critically acclaimed and was named the "Adventure Game of the Year" by GameSpot in 1999. In 2001, Appeal developed a sequel, called Outcast II: The Lost Paradise, which was never finished due to bankruptcy. In 2010, the game was re-released via digital distribution on GOG. In 2014, Outcast was remastered as Outcast 1.1, after the original developers reacquired the franchise intellectual property. In 2017, a remake titled Outcast: Second Contact was released for Windows, PlayStation 4, and Xbox One. A sequel, Outcast: A New Beginning, is scheduled to be released for Windows, PlayStation 5 and Xbox Series X/S.

<span class="mw-page-title-main">Surfel</span>

Surfel is an abbreviated term for a "surface element," analogous to a "voxel" or a "pixel". In 3D computer graphics, the use of surfels is an alternative to polygonal modeling. An object is represented by a dense set of points or viewer-facing discs holding lighting information. Surfels are well suited to modeling dynamic geometry, because there is no need to compute topology information such as adjacency lists. Common applications are medical scanner data representation, real time rendering of particle systems, and more generally, rendering surfaces of volumetric data by first extracting the isosurface.

<span class="mw-page-title-main">Software rendering</span> Generating images by computer software

Software rendering is the process of generating an image from a model by means of computer software. In the context of computer graphics rendering, software rendering refers to a rendering process that is not dependent upon graphics hardware ASICs, such as a graphics card. The rendering takes place entirely in the CPU. Rendering everything with the (general-purpose) CPU has the main advantage that it is not restricted to the (limited) capabilities of graphics hardware, but the disadvantage is that more transistors are needed to obtain the same speed.

In computer graphics, per-pixel lighting refers to any technique for lighting an image or scene that calculates illumination for each pixel on a rendered image. This is in contrast to other popular methods of lighting such as vertex lighting, which calculates illumination at each vertex of a 3D model and then interpolates the resulting values over the model's faces to calculate the final per-pixel color values.

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

Volume ray casting, sometimes called volumetric ray casting, volumetric ray tracing, or volume ray marching, is an image-based volume rendering technique. It computes 2D images from 3D volumetric data sets. Volume ray casting, which processes volume data, must not be mistaken with ray casting in the sense used in ray tracing, which processes surface data. In the volumetric variant, the computation doesn't stop at the surface but "pushes through" the object, sampling the object along the ray. Unlike ray tracing, volume ray casting does not spawn secondary rays. When the context/application is clear, some authors simply call it ray casting. Because ray marching does not necessarily require an exact solution to ray intersection and collisions, it is suitable for real time computing for many applications for which ray tracing is unsuitable.

<span class="mw-page-title-main">Computer graphics</span> Graphics created using computers

Computer graphics deals with generating images and art with the aid of computers. Today, computer graphics is a core technology in digital photography, film, video games, digital art, cell phone and computer displays, and many specialized applications. A great deal of specialized hardware and software has been developed, with the displays of most devices being driven by computer graphics hardware. It is a vast and recently developed area of computer science. The phrase was coined in 1960 by computer graphics researchers Verne Hudson and William Fetter of Boeing. It is often abbreviated as CG, or typically in the context of film as computer generated imagery (CGI). The non-artistic aspects of computer graphics are the subject of computer science research.

<span class="mw-page-title-main">Grome</span> 3D terrain generation software

Grome is an environmental modeling package developed by Quad Software dedicated for procedural and manual generation of large virtual outdoor worlds suitable for games and other 3D real-time simulation applications.

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

Voxel Space was a voxel raster graphics rendering engine invented by Novalogic developer and vice-president of technology, Kyle Freeman. The company was issued a patent for the technology in early 2000.

This is a glossary of terms relating to computer graphics.

References

  1. ↑ Chmielewski, Sz., Tompalski, P. (2017). "Estimating outdoor advertising media visibility with voxel-based approach". Applied Geography, 87:1–13 doi : 10.1016/j.apgeog.2017.07.007. Preprint download: "Estimating outdoor advertising media visibility with voxel-based approach (PDF Download Available)". Archived from the original on 2017-10-02. Retrieved 2017-10-02.
  2. ↑ Shchurova, Catherine I. (2015). "A methodology to design a 3D graphic editor for micro-modeling of fiber-reinforced composite parts". Advances in Engineering Software. Advances in Engineering Software Volume 90, December 2015, Pages 76-82. 90: 76–82. doi:10.1016/j.advengsoft.2015.07.001.
  3. 1 2 Foley, James D.; Andries van Dam; John F. Hughes; Steven K. Feiner (1990). "Spatial-partitioning representations; Surface detail". Computer Graphics: Principles and Practice. The Systems Programming Series. Addison-Wesley. ISBN   978-0-201-12110-0. These cells are often called voxels (volume elements), in analogy to pixels.
  4. ↑ "Voxels". tnlc.com. Archived from the original on 2014-04-17.
  5. ↑ Outcast manual. Infogrames. 1999. p. 34.
  6. ↑ Bertuch, Manfred (2009). "'Klötzchenwelten' [Worlds of little blocks] in c't Magazin issue 04/2009". C't: Magazin für Computertechnik. Hannover: Heise Zeitschriften Verlag GmbH & Co. KG: 183. ISSN   0724-8679.
  7. ↑ "OUTCAST – Technology: Paradise". archive.org. 7 May 2006. Archived from the original on 7 May 2006.
  8. 1 2 "Voxel terrain engine Archived 2013-11-13 at the Wayback Machine ", introduction. In a coder's mind, 2005.
  9. ↑ "A Little Bit Of History – Next-Gen 3D Rendering Technology: Voxel Ray Casting". tomshardware.com. 21 October 2009.
  10. ↑ "Kyle G. Freeman Inventions, Patents and Patent Applications – Justia Patents Search". justia.com. Archived from the original on 2014-02-01.
  11. ↑ "FlightSim.Com – NovaLogic Awarded Patent For Voxel Space Graphics Engine". flightsim.com. Archived from the original on 2015-09-24.
  12. ↑ Novelline, Robert. Squire's Fundamentals of Radiology. Harvard University Press. 5th edition. 1997. ISBN   0-674-83339-2.
  13. ↑ Society, The Optical. "High-speed laser writing method could pack 500 terabytes of data into CD-sized glass disc". phys.org. Retrieved 2021-10-31.
  14. ↑ "Review Crew: Amok". Electronic Gaming Monthly . No. 93. Ziff Davis. April 1997. p. 53.
  15. ↑ "A brief history of Voxel games. | DjArcas's Blog". Archived from the original on 2013-12-18. Retrieved 2013-12-18.
  16. ↑ "Chunk format: Block format". Minecraft Wiki. Retrieved 24 September 2023.
  17. ↑ "Tutorials/Units of measure: Distance". Minecraft Wiki. Retrieved 24 September 2023.
  18. ↑ "Appeal S.A. - MobyGames". mobygames.com. Archived from the original on 2014-12-19.
  19. ↑ Zak, Robert (4 April 2016). ""There's never been a better time": Planet Coaster rides to meet the demand for deep simulation games". Archived from the original on 4 July 2016. Retrieved 11 July 2016.
  20. ↑ "Trove – A Voxel MMO Adventure from Trion Worlds". trovegame.com. Archived from the original on 2014-07-22.
  21. ↑ "VANGERS". kdlab.com. Archived from the original on 2010-01-14. Retrieved 2009-12-20.
  22. ↑ Ars Technica (14 January 2011). "We <3 voxels: why Voxatron is an exciting indie shooter". Archived from the original on 2011-10-13.
  23. ↑ "Lexaloffle BBS :: Voxatron". lexaloffle.com. Archived from the original on 2011-01-08. Retrieved 2011-01-12.
  24. ↑ Hickson, Steven; Birchfield, Stan; Essa, Irfan; Christensen, Henrik (2014). "Efficient Hierarchical Graph-Based Segmentation of RGBD Videos". 2014 IEEE Conference on Computer Vision and Pattern Recognition. pp. 344–351. arXiv: 1801.08981 . doi:10.1109/CVPR.2014.51. ISBN   978-1-4799-5118-5. S2CID   519623.
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.