Concept
Binary space partitioning
Related concepts (17)
Quake engine
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 is now licensed under the terms of GNU General Public License v2.0 or later. After release, the Quake engine immediately forked. Much of the engine remained in Quake II and Quake III Arena. The Quake engine, like the Doom engine, used binary space partitioning (BSP) to optimise the world rendering. The Quake engine also used Gouraud shading for moving objects, and a static lightmap for non-moving objects.
Octree
An octree is a tree data structure in which each internal node has exactly eight children. Octrees are most often used to partition a three-dimensional space by recursively subdividing it into eight octants. Octrees are the three-dimensional analog of quadtrees. The word is derived from oct (Greek root meaning "eight") + tree. Octrees are often used in 3D graphics and 3D game engines. Each node in an octree subdivides the space it represents into eight octants.
Collision detection
Collision detection is the computational problem of detecting the intersection of two or more objects. Collision detection is a classic issue of computational geometry and has applications in various computing fields, primarily in computer graphics, computer games, computer simulations, robotics and computational physics. Collision detection algorithms can be divided into operating on 2D and 3D objects. In physical simulation, experiments such as playing billiards are conducted.
Hidden-surface determination
In 3D computer graphics, hidden-surface determination (also known as shown-surface determination, hidden-surface removal (HSR), occlusion culling (OC) or visible-surface determination (VSD)) is the process of identifying what surfaces and parts of surfaces can be seen from a particular viewing angle. A hidden-surface determination algorithm is a solution to the visibility problem, which was one of the first major problems in the field of 3D computer graphics .
K-d tree
In computer science, a k-d tree (short for k-dimensional tree) is a space-partitioning data structure for organizing points in a k-dimensional space. k-d trees are a useful data structure for several applications, such as searches involving a multidimensional search key (e.g. range searches and nearest neighbor searches) and creating point clouds. k-d trees are a special case of binary space partitioning trees. The k-d tree is a binary tree in which every node is a k-dimensional point.
First-person shooter
First-person shooter (FPS) is a sub-genre of shooter video games centered on gun and other weapon-based combat in a first-person perspective, with the player experiencing the action through the eyes of a protagonist or antagonist which is armed, and then controlling the player character in a three-dimensional space. The genre shares common traits with other shooter games, and in turn falls under the action game genre. Since the genre's inception, advanced 3D and pseudo-3D graphics have challenged hardware development, and multiplayer gaming has been integral.
Ray casting
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.
First-person shooter engine
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. The development of the FPS graphic engines is characterized by a steady increase in technologies, with some breakthroughs.
Game engine
A game engine is a software framework primarily designed for the development of video games and generally includes relevant libraries and support programs such as a level editor. The "engine" terminology is similar to the term "software engine" used in the software industry. The game engine can also refer to the development software utilizing this framework, typically offering a suite of tools and features for developing games. Developers can use game engines to construct games for video game consoles and other types of computers.
Space partitioning
In geometry, space partitioning is the process of dividing a space (usually a Euclidean space) into two or more disjoint subsets (see also partition of a set). In other words, space partitioning divides a space into non-overlapping regions. Any point in the space can then be identified to lie in exactly one of the regions. Space-partitioning systems are often hierarchical, meaning that a space (or a region of space) is divided into several regions, and then the same space-partitioning system is recursively applied to each of the regions thus created.