Introduction
3D computer graphics have had a massive impact on how we interact with digital environments. Whether it be through video games, animated films, virtual reality environments or architectural visualisations, there is a lot of complex mathematics involved known as computational geometry. This is used by computers to help visualise, understand, manipulate and calculate objects in a 3D environment. This has an impact on every aspect of virtual characters, animated environments, digital objects and interactive environments.
Without using computational geometry to calculate the geometry of objects it would be extremely difficult to create complex and realistic digital environments. Computational Geometry in Computer Graphics helps allow us to translate mathematical geometry into visual environments. This helps with many aspects of computer graphics such as polygon modelling, mesh creation, transformations, surface rendering, collision detection and organisation.
Computational Geometry in 3D Computer Graphics
Computational geometry is a branch of both computer science and mathematics. It helps develop algorithms to help solve problems involving geometry. This helps computers understand and calculate how to represent shapes, distances, intersections, spatial analysis and manipulate objects in a 2D/3D environment. In computer graphics this helps computers understand the structure of virtual objects. For example when an object such as a building, vehicle or animated character are created in a game, the software will use geometry to determine the size, surfaces, vertices and position of the object. This allows graphics software to efficiently calculate complex objects. Computational geometry helps with many aspects of graphics such as modelling, animation, lighting and rendering.
Computational geometry is an important aspect of creating 3D objects in computer graphics. Unlike physical objects there are no actual surfaces or physical elements to the object. Instead there will be mathematical data to represent the object. This will be processed by the computer using geometry calculations to work out what should be shown to the user, how the surfaces should react to lighting and how it should interact with other objects. This can get very complex when there are lots of objects in a scene. Computational geometry helps by providing methods to help organise this data so not every calculation needs to be done from scratch. This allows modern graphics software to create complex visual environments.
Using Polygons and Meshes in 3D Modelling
One of the most important aspects of using geometry in 3D computer graphics is using polygons. A polygon is a flat closed shape that is made up of straight lines between points known as vertices. Triangles, squares and other shapes with multiple sides can be used to create digital objects. A polygon can be used to create the surfaces of buildings, vehicles, landscapes, furniture and virtual characters. This helps to create the structure of the object. Triangles are especially important as they’re simple to calculate mathematically. Graphics software often uses triangles to calculate complex surfaces. This makes using polygon modelling a good choice.
A polygon mesh is a collection of vertices, edges and polygonal faces that form the surface of a 3D object. Vertices are specific points in space whilst edges help connect the vertices together. This helps artists and developers create objects of various complexities. For example a simple character in a game may only have a small amount of polygons in the mesh. However if an object is very detailed such as a digital human character, it may have thousands or millions of polygons. This helps make it easier to edit individual sections of the object. Developers can edit the vertices, add faces, remove extra geometry and improve the surfaces. This makes polygon meshes an important aspect of modelling characters, environments, and products.
Using Triangulation
Triangulation is a technique used in computational geometry where a polygon or other shape can be split into triangles. This is commonly used in computer graphics as triangles are easy to calculate. Graphics software can easily calculate triangular surfaces rather than irregular polygons. This helps with lighting, shading and transforming objects. An example would be if there was a large polygon representing part of a building or landscape, this can be split into multiple triangles to help the graphics engine calculate individual sections. Triangulation helps make sure different graphics systems are compatible as triangles are a standard geometric primitive. Complex shapes can be split into smaller triangles to help with geometry calculations.
This is also an important aspect of animation and games. When an animated character moves, the mesh may need to be calculated multiple times. Triangular geometry helps make this easier to calculate. Triangulation can also be used to create landscapes. Large virtual landscapes can be split into triangular surfaces. Individual vertices can be moved to change how the landscape looks. Different triangulation techniques can be used to help reduce extra complexity. This helps with modelling, rendering and animating.
Geometric Transformations
Geometric transformations are mathematical calculations that help move, rotate, scale and change the shape of objects in a 3D environment. This is important in computer graphics as virtual objects need to be placed in certain spots. The most common types of transformations are translating, rotating and scaling. Translating will move an object from one place to another. Rotating will change the direction the object is facing. Scaling will make the object bigger or smaller. This helps move furniture inside buildings, vehicles along roads and changing the size of objects. This also helps with animation as characters need to constantly move and change their positions.
Modern graphics systems often use transformation matrices. This is a mathematical structure that helps computers calculate how to change the coordinates of an object. Multiple transformation matrices can be added together to help with multiple movements and changes. For example a character can be moved forward, rotated to face another character and change their position. This can also be used in camera systems. Geometric transformations help determine the position, direction and perspective of the camera. This helps to determine how objects relate to each other. Without geometric transformations it would be much harder to create cohesive movements, interactive environments and realistic camera perspectives.
Surface Modelling
Surface modelling helps to determine the surfaces of 3D objects. This is important when Creating Realistic Digital Objects. If an object has smooth, curved, irregular or complex surfaces, surface modelling can help create a realistic representation. This can create more complex shapes and smooth surfaces compared to simple polygon modelling. Techniques such as spline modelling, Bézier surfaces and NURBS can help create curved surfaces mathematically. These can be helpful when creating vehicles, aircraft, furniture, buildings and complex characters. Computational geometry can help with these processes by providing algorithms to help calculate curves, connect surfaces and control the shape of digital objects.
Surface modelling is also important when creating characters. Realistic characters need to have well designed facial features, body shapes, clothing etc. Animation software will use geometric information to determine how the surfaces should react. For example when a digital character bends their arm or turns their head, the surrounding mesh and surfaces will need to change to look realistic. Extra techniques such as subdivision surfaces can be used to help create smooth surfaces from polygon meshes. This allows artists to start with simple geometric shapes and create more detailed surfaces. Computational geometry helps to create realistic digital objects by combining mathematical modelling with artistic design.
Using Computational Geometry for 3D Animation
3D animation helps create the illusion of movement by changing the position, direction and shape of digital objects. Computational geometry helps provide the mathematical calculations needed to calculate the changes. Animation software will use geometric algorithms to move characters, rotate objects, change body positions and create interactions. For example when a virtual character is walking, their legs, arms, torso and head will need to move. This will depend on the geometric relationships between different body parts. This can be calculated using animation systems.
Skeletal animation can also be used. This is a technique where a skeleton of connected bones is used to animate a digital character. Each bone will affect specific parts of the mesh. This helps to make the model move without having to manually move every vertex. Computational geometry can help calculate how the connected parts should be rotated, translated and deformed. Inverse kinematics can also be used to calculate joint positions so that a character’s hand/foot/body part can be placed in a specific spot. This can be helpful when characters are interacting with objects or moving over uneven surfaces. Physics animation can also be used to help represent how objects move. This helps animation software create more realistic characters, movements and complex virtual environments.
Spatial Partitioning
Spatial partitioning helps organise objects in a 3D environment. This can help graphics software create complex scenes. This is especially important in games and simulations where there can be thousands of objects. Without this the graphics engine may need to check every object which can affect performance. Spatial partitioning helps organise objects efficiently. Common types of spatial partitioning include spatial grids, octrees, bounding volume hierarchies and binary space partitioning trees. Each type of spatial partitioning will organise the geometry in a different way depending on the type of virtual environment.
Octrees help divide a 3D environment into smaller sections. These can be further divided if needed. This helps applications organise objects based on where they are. Bounding volume hierarchies help organise objects or groups of objects using simple shapes. This helps identify any potentially relevant objects. Spatial partitioning can be very useful in large open world games, architectural visualisations and VR environments. This helps the graphics engine focus on objects that are relevant. This reduces any unnecessary geometry calculations.
Collision Detection
One of the most important uses of computational geometry is collision detection in games. This determines if two or more objects overlap in a virtual environment. This is needed to ensure interactive environments function as expected. For example if a player controlled character approaches a wall the game engine needs to recognise there has been a collision and stop the character from passing through the solid object. If a virtual ball hits the floor the system needs to recognise there has been an interaction. This uses geometric representations such as bounding boxes, spheres, capsules and more detailed polygons. This helps game engines identify potential collisions.
Many modern game engines will use a two step process to help improve efficiency. The first step is the broad phase which helps identify pairs of objects that may collide using simple boundaries and spatial partitioning. The second step is the narrow phase which helps identify if there actually is a collision. This reduces any unnecessary calculations. Collision detection also works with physics to calculate how objects react to collisions, gravity, friction etc. For example if a character pushes a virtual object the game engine can calculate how it should move. This helps make interactive environments more realistic.
Optimising Rendering
Rendering helps convert 3D scene information into 2D. This involves processing geometry, camera positions, lighting, materials, textures and more. Whilst modern graphics hardware can handle vast amounts of geometry there can still be a lot of strain on the computing resources if there are complex scenes. Computational geometry can help optimize rendering by reducing unnecessary calculations. Level of detail can be used to help reduce complexity. This helps change how detailed an object is based on how far away it is from the camera. For example a detailed building that is close to the camera may have a high resolution model. However if it is further away it may have a simpler model as it won’t look as detailed.
Frustum culling, occlusion culling and back-face culling can be used to help optimize rendering. Frustum culling removes objects outside of the camera’s view. Occlusion culling helps identify objects that are hidden behind other objects. Back-face culling stops the graphics system from rendering any faces of polygons that are not facing the viewer. This helps reduce the amount of geometry being processed. Computational geometry can also help optimise mesh simplification. This helps reduce the amount of polygons in a model whilst trying to keep the shape. This helps keep the graphics engine running smoothly whilst rendering detailed environments. This is especially important in modern games as images need to be constantly generated.
Using Computational Geometry in Game Engines
Game engines use a mixture of technologies and algorithms to create, manage and display interactive virtual environments. Computational geometry plays a key role in many aspects of game engines. Popular engines such as Unity and Unreal Engine use geometry structures and algorithms to help with 3D modelling, animation, physics, lighting and rendering. Developers can import digital models, place objects in virtual environments, set collision boundaries and control how characters interact with their environment. Tools can also be provided to manipulate vertices, meshes, materials and spatial relationships. This helps developers create complex environments without having to create every geometric algorithm.
Computational geometry can also be used to procedurally generate digital environments/objects. Geometric algorithms can be used to create roads, buildings, plants, mountains and more. This can be very useful in open world games as it would take a lot of time to design every section of a large environment manually. Procedural generation can also help create variety in terrains, buildings and environments. Game engines use geometry calculations to help manage character movement, camera positioning, object placement and interactions. As graphics continue to improve these algorithms are essential to creating larger, detailed and interactive games.
Creating Realistic Characters and Environments
To create realistic characters a mix of geometry, surface modelling, animation and rendering techniques are used. Artists will create a 3D representation of their character using vertices, edges and polygonal faces. They will then add extra detail to the model such as facial features, clothing, hair and body. Computational geometry can help ensure everything fits together and looks consistent. Mesh deformation, subdivision surfaces and interpolation can be used to create smoother models and extra detail on the characters. Once the model has been created rigging and animation systems will use geometry calculations to help move the model. This helps digital characters walk, run, turn, interact with objects and show emotions through changes in their facial geometry.
The same applies to creating realistic digital environments. Buildings, roads, trees, mountains, furniture and more can all be represented using geometry. Different modelling techniques can be combined to create environments of varying complexity. Surface modelling and texturing can help improve how the objects look. Lighting and shading can help add depth and realism. Computational geometry can help place objects in the environment. This combines geometry modelling with animation and rendering to create digital environments that look like real life locations but still gives artists creative freedom.
Computational Geometry in Virtual Reality and Augmented Reality
Virtual reality (VR) and augmented reality (AR) both provide an immersive experience for the user through combining digital content with interactive components. Virtual reality immerses the user into a digitally created environment whereas augmented reality overlays digital content onto our physical environment. Computational geometry is heavily used in both virtual and augmented reality environments due to having to accurately represent digital objects. In virtual reality environments, geometric computations are used to create immersive environments for the user to interact with and view from various angles. As the user moves around the environment, the virtual camera needs to constantly update its position and rotation. This means that the environment can react quickly to users turning their heads, changing directions and moving around the virtual environment.
Augmented reality relies on geometric algorithms to place digital objects within the physical environment. An example would be having a piece of virtual furniture in an AR application, the software would need to estimate the size of the room, identify surfaces and compute where the object should go. Computational geometry helps with this by helping to map out the space, identify surfaces and transform coordinates to track the objects. This ensures the digital objects stay in place as the user moves around the environment. Accurate geometric computations are important to ensure the virtual objects are placed correctly, if they are not then the immersive experience will not look as realistic. As these technologies grow, computational geometry will help to allow more responsive interactions, realistic digital objects and increasingly advanced immersive applications.
Challenges and Future Development of Computational Geometry
Computational geometry can be quite challenging to implement within modern computer graphics and games. As models become increasingly complex, there is a lot of information to process. Complex models such as detailed characters, realistic landscapes and large interactive environments all have large amounts of geometric data which will take a lot of computing power to process. Developers need to find a balance between making the environment look nice whilst ensuring it runs efficiently. This can be done by choosing the correct modelling techniques, simplifying the models and using efficient rendering algorithms. With complex animations and physics, keeping everything accurate can be challenging. As animations get more complex, there is constantly a need to calculate geometry.
As graphic technologies improve, computational geometry will become more important. Artificial intelligence is being explored within the industry to help with tasks such as automatically modelling 3D objects, generating meshes, textures and helping with animations. This helps artists and developers create complex digital assets more efficiently. However, it is still important to have accurate geometric objects. With improvements within graphics processors, real time rendering and spatial computing, there are more opportunities to create detailed and responsive virtual environments. Improvements within procedural modelling and optimising geometry may also help to make large digital worlds easier to create. As virtual reality, augmented reality, digital simulations and interactive entertainment continue to improve, computational geometry will be an important part of creating accurate, efficient and realistic 3D environments.
Conclusion
Computational geometry is a fundamental part of modern 3D computer graphics, animation and games. It provides us with the maths and algorithms needed to represent objects within a virtual environment. Techniques such as polygons, meshes, triangulation, transformations, surface modelling and partitioning are used throughout almost all parts of digital content creation. This makes it possible to perform key tasks such as animating objects, collision detection, optimising rendering and procedurally generating environments.
Modern game engines use these techniques to create interactive environments, realistic characters and realistic interactions between objects. Virtual and augmented reality applications rely on this to provide accurate and immersive experiences. As graphic technologies continue to improve, computational geometry will be an essential tool to improve the visuals, efficiency and interactivity. It has uses outside of entertainment too and can be used within architecture, engineering, education and scientific visualisation.
