Destruction in Video Games: The Final Part

As I mentioned yesterday, today is all about Shape Matching Methods for destruction in video games. Conceptually, these methods are easier to understand than Finite Element Methods, but mathematically, they are roughly just as difficult as FEM. So to avoid lengthy mathematical equations, let's just talk about it conceptually. 

Recall that Finite Element Methods depend mostly on the physical properties of the object's material for simulation and are meshed. Shape Matching Methods are geometrically based and work with meshfree models. Meshfree models don't depend on a collection of connected points. As their name implies, they depend on the shape of the object directly! These methods don't require expensive decomposition or computations like FEM, which make them a lot faster for certain cases (specifically simple deformations on more rigid objects)

Shape Matching Methods are useful for meshless deformations, since they rely only on geometric constraints and distances between points instead of internal energies like FEM. The algorithm for meshless deformation is decently simple to understand. Given that you have a bunch of particles with mass in some starting configuration (i.e. arrangement), we can draw a "simulated mesh" connecting these particles to define some shape of this starting configuration. Note that these particles are NOT connected in an actual mesh and we assume there isn't any particle-particle interaction between them. These particles are simulated and respond to collisions or external forces only. We also assume that we have no idea of their connectivity to each other; we are just defining some shape (configuration) that we will later match after deformation occurs. Also note that these shapes can be anything. It really depends on the way the particles are set up. So now let's say we apply some external force to this "simulated mesh." What happens is that the particles of the original configuration begin to deform and we see rotations and translations of these deformed points begin to occur. With the new positions of these deformed points, we match the original shape (configuration) near the new positions of the particles to determine the optimal rotation and translation of the original shape to get "goal points". These "goal points" represent the original shape of our starting configuration except rotated and translated to define the directions that our deformed particles should move in to reach the goal points. In other words, we need these "goal points" to figure out the directions our points should move in to end up with the same shape we started with, except rotated and translated. That's why it is called shape matching!

Essentially we:

1. start with a bunch of particles in some shape,

2. we apply forces to deform these points from the starting configuration,

3. we align that same starting shape (except with the points rotated and translated) to the newly deformed particles' positions (goal points),

4. and we move those deformed points towards the goal points to get the original shape we started with!

Check out the image below to help understand what I mean! It makes a lot of sense with a pictorial representation!

Shape Matching Methods are mainly suited for stiff or nearly rigid objects, and thus they can be problematic with objects that need to undergo large amounts of deformation. You can extend the range of motion by accounting for Linear or Quadratic deformations.

In terms of speed, ease of use, and quality of animation, Shape Matching Methods are generally very good. They're pretty fast and can simulate hundreds of SIMPLE deformations of objects in real-time.

Here is a helpful link to learn more about Shape Matching Methods, the mathematics behind it, and where I received the image below!

https://www.cs.drexel.edu/~david/Classes/Papers/MeshlessDeformations_SIG05.pdf

Destruction in 3D Video Games: Part 4

I've been reading up a lot on a thesis called Procedural Destruction of Objects for Computer Games by Joris van Gestel. Today I want to talk about one section of his thesis, which discusses previous work on procedural destruction. Van Gestel mentions that he sent a questionnaire out to a variety of game companies and asked them what they thought the most important aspects were for destruction in video games. From his results, he found out that "the five most important aspects were control, speed, ease of use, ease of integration, and the quality of the result." Surprisingly, none of those companies thought "realism" was an important aspect, as long as the destruction in the game seemed good enough.

Van Gestel mentions that the most common approaches to destruction in video games nowadays are Finite Element Methods (FEM) and Shape Matching Methods. 

For today I'm going to talk briefly about FEM. Tomorrow I will discuss Shape Matching.

Finite Element Methods (FEM) are considered numerical techniques for solving many different kinds of mechanical engineering problems and mathematical physics problems. These are commonly used in computer graphics as well for destruction! In terms of destruction, FEM work on meshed 3D models. Think of meshed models as 3D models that rely on a grid of interconnected simulation vertices. Finite Element Methods use these meshed models to determine "how forces propagate through a continuous volume, usually the inside of an object", as Van Gestel states; this helps us analyze crack initiation and how that crack propagates throughout the rest of the object's volume in a video game, depending on that object's actual material. These existing techniques of FEM utilize the external forces on the object and relate them to the internal forces on the object using the object's material properties. Through analyzing these internal forces, FEM can determine where the object will crack and in what direction to propagate the crack even further! 

The internal forces acting on the object are calculated node by node in the FEM mesh. For those confused on what a 'node' is, it is just a vertex (or point) in the mesh. For each node, the internal force on that node can be decomposed into two components: a tensile component and a compressive component. With these two force components (tensile and compressive), we can combine them together mathematically and treat them as a single "separating" force (discarding any unbalanced forces) that is used for indicating whether or not material failure (fracturing) occurs at that specific node. If this separating force has a magnitude larger than that of the material's toughness, then a crack is initiated and will most likely propagate. If there was material failure as a result of this separating force, we can find the plane of fracture on the current node and then split along that plane! After the current node is split, the algorithm continues on to calculate the separating forces on remaining vertices and repeating this whole process. This is the simplified representation of Finite Element Methods with destruction in video games.   

You may be asking: "I'm a little confused. How do we know where the object is cut?" Well, it gets a little mathematical. This separating force is really calculated using a mathematical entity called Tensors. If you are confused or if you'd like me to explain the exact mathematics behind it, let me know in the comments below or contact me individually! 

Anyway, Finite Element Methods generate super realistic results! However, the downside of using FEM is speed. It is very, very, very slow. For just a one-second animation, it can take up to 6 hours! This is partly due to the splitting of nodes along the fracture plane. As you increase the number of split nodes, the total number of nodes in the simulation also increases. More nodes in a simulation means more time to render! Thus as an object starts to fracture, the number of nodes in the simulation increases and that slows down rendering time. These methods are usually hard to implement in code too (again, due to Tensors)

Car crash deformation with FEM

Retrieved from https://en.wikipedia.org/wiki/Finite_element_method

Destruction in 3D Video Games: Part 3

We covered a lot of content already! I plan on covering Destruction a few more days (probably 2 more days).

To take a breather for today, I just briefly want to discuss the difference between Ductile materials and Brittle materials!

• Ductile Materials - These are materials that are able to undergo extensive amounts of plastic deformation before any sort of fracturing occurs. In other words, these are "tough" materials that absorb a lot of energy and are hard to break under high amounts of stress and strain. Examples of these materials include Copper, Steel, and Aluminum.

• Brittle Materials - These are materials that can only endure relatively small amounts of plastic deformation before fracturing. In other words, these are "weak" materials that DON'T absorb much energy when placed under stress and can only endure a small amount of strain. These materials do deform elastically and plastically but only by very small amounts before fracturing. Examples include most glasses and ceramics.

Destruction in 3D Video Games: Part 2

Welcome back!

Today is all about the Physics of Destruction. I'm going to discuss different types of deformation as a result of different types of forces and stress vs. strain. 

In material sciences and engineering, Deformation is defined as the change in an object's shape, size or structure as a result of applied forces or changes in temperature. For now, I'm only going to discuss forces. There are different types of applied forces that can cause deformation: 

• Tensile Forces - These types of forces are pulling forces, or tension forces. These are forces that pull in opposite directions of the material and are intended to stretch or lengthen the object. For example, consider a rubber band. If you wrap one finger on both ends of the rubber band and pull in opposite directions with your fingers, you would see the rubber band start to stretch! That would be a Tensile Force!

• Compressive Forces - These types of forces are pushing forces. These are forces that push inward towards the material and are intended to squeeze or shorten the object. For example, consider an empty soda can. Sometime people like to show off their strength by putting their hands on both ends of the can and pushing inward to crush the can. This would be a Compressive Force!

• Shear Force - This is a type of unaligned force that pushes one part of a material in one direction and another part of that material in the opposite direction. For example, consider a deck of cards. When you push the top of a deck of cards in one direction, and the bottom of the deck in the opposite direction, you will see the deck move in two opposite directions. Shear forces can cause cracking or tearing of the material.

And here are other concepts related to deformation that result from forces, but they aren't forces themselves:

• Bending (Flexure) - The behavior of a structural material that is subjected to some force perpendicular to its longitudinal axis. (see picture below)

• Torsion - Also known as twisting, as a result of torque. (see picture below)

Now, I also mentioned how there were different types of deformation. The three different kinds of deformation include:

1. Elastic Deformations - These are reversible deformations, meaning that as soon as the applied force of this material is removed, the material will return to its original shape. For example, consider a couch pillow. When you push your foot down on the pillow a fair amount, and then lift it up after some time, most pillows will go back to their original form.

2. Plastic Deformations - These are irreversible deformations, meaning that these materials will not resume their original shape after an applied force is removed. This is the 2nd stage of deformation. Before an object can undergo Plastic Deformation, it MUST first undergo Elastic Deformation, even if only by a small amount! Consider a piece of metal. If you apply a decent amount of force to the object, you will notice that it won't return to its original shape. It'll be reshaped and restructured.

3. Fractures - These are also irreversible deformations, except these deformations result in the material breaking and being split into two or more different pieces as a result of excessive stress. This is the 3rd and final phase of Deformation, where the material first has to undergo Elastic Deformation and then Plastic Deformation, THEN fracturing. Consider breaking a stick for a bonfire. When you bend a big, rigid branch far enough, it will usually snap into two different pieces! That would be a Fracture!

And finally, I wanted to clarify the different between stress and strain. 

• Stress = the applied force per unit area of a material. This is a vector, since it has a direction!

  • σ = F / A where σ = stress, F = force applied, and A= cross sectional area of the object.

• Strain = the deformation of a material or object due to excessive stress beyond that object's maximal stress load. Too much stress causes strain! Strain is what causes the different types of deformation, as seen in the Stress-Strain chart below.

Stress-Strain Model

Received from https://en.wikipedia.org/wiki/Deformation_(engineering)

Bending structural beam

Retrieved from https://en.wikipedia.org/wiki/Bending

Torsion

Retrieved from https://en.wikipedia.org/wiki/Torsion_(mechanics)

Destruction in 3D Video Games: Part 1

I recently was out for a walk around my neighborhood a couple weeks ago, and as the critical thinker that I am, I began contemplating the universe. I was thinking about how video games are incredibly powerful because of the virtual worlds that game developers could literally "build and destroy" with their own imagination and the right tools. I then started to think about how games could be made more realistic and more enjoyable with destructible environments and material physics! After seeing the Crackdown 3 gameplay trailer a few years back, I became interested in applying realism to gaming. As a side note, These topics can also be applied to different forms of engineering, real-world simulation testing, and even VR as well! 

For today, I'm going to briefly discuss some background information on 3D models and how that connects to Destruction in video games.

For starters, a Mesh is a collection of vertices, edges, and faces that structure and shape a 3D game object. Think of a mesh as a lattice-structure of these vertices and edges that represents the geometry of that 3D game object.

Most of the time, 3D game development tends to follow this process:

Game development always starts with thinking about ideas for every aspect of the game, which includes things like the story, characters, gameplay mechanics, theme, style, etc. Once these have been formally laid out, the developers decide which ideas will most likely be implemented in the actual game. Then the concept artists are put to work to create generalized sketches, or even technical sketches with dimensions and multiple perspectives, of the game objects and game environment. The concept art helps the 3D modeling artists to begin constructing virtual 3D meshes that depict the game objects. After a 3D model has been created, it has to be UV-mapped.  UV-Mapping is the process of taking the complex geometry of a mesh (i.e. its triangles, polygons, and n-gons) and projecting that geometry onto a flat 2D grid to prepare for texturing. They use the term "UV Unwrapping" to describe this process. The UV part refers to the coordinate axes. The axes are labeled (u,v) instead of the classic (x,y) in Cartesian coordinates. Once you have these UVs laid out properly, you can layer an image onto the surface of the 3D model. This image to be wrapped around the surface of the 3D model is called a Texture. Textures are what make game objects seem more realistic and they make these objects have a "look" and "feel" to them. Then the game object is ready to be exported and used in a game engine! Yet, it's easier said than done of course!  :)

Now, here is the part on how 3D models relate to destruction.

There are a few limitations to mesh deformation in video games. Here's why: A while back, game developers traditionally meant for 3D models to be "static" in the game world, meaning the mesh (i.e. its geometry) and textures weren't meant to be changed at all when the game was running. Sure, these 3D game objects could be moved (translated), rotated, or even scaled at runtime, but that never changed the virtual geometry of the mesh. Due to the massive computational load on many computers, 3D models are usually intended to be static entities. Yet nowadays, changes to a game object are often desired by game developers. By "changes", I mean object deformation and destructibility, whether that be through colliding with another object, the player physically applying force to an object, etc. 

Since computers have gotten more and more powerful over the last few years, a lot of game companies are trying to uncover new techniques to make these "changes" possible at runtime. 

For example, suppose you are driving your favorite car extremely fast in a game. You suddenly lose control and smash into a concrete barrier with the front of your car! Oh no! Normally, the player would expect the front end of the car to take damage and have massive deformation, such as the hood now being dented, the paint scraped off, the bumper hanging on by a thread, or whatever. In this example, one problem developers face is calculating the area of impact, the amount of damage the car took, and what parts of the car should deform in a seemingly realistic sort of way. Another major problem would be the car's UV mapping and texturing. The UVs and the textures of that object would need to be recalculated and updated after every single collision (given that deformation occurs). If developers don't update the UV maps (or if they don't recalculate the UVs correctly) then the textures wouldn't map correctly to the mesh and the game object would look TERRIBLY unrealistic in the game!

One work-around for this limitation would be for developers to create other separate 3D models of the same object, each of which represents a varying amount of destructive damage on that object. The good news is that each one of these meshes of varying amounts of damage only have to be UV mapped and textured ONCE, and thus requires no updating when the game is running. Then, when that object receives a certain amount damage in the game world, that object is removed from the scene altogether and replaced by the more damaged 3D model of the same object. This switch in meshes happens in-between update frames, so the player (almost always) cannot tell this has happened! The limitation of this approach is that the developers would have to create a TON of different 3D models that are all UV mapped and textured in order to make the game feel very realistic. It also would be super hard to accurately control which mesh to replace. What do I mean by this? Consider the car example again. Let's say you only have four levels of destructive damage to your car (that is, four different 3D models of the same car with different amounts of damage). If your car gets side-swiped by another car in the game, the player would expect some scratches or dents on that specific side of the car. It would seem very inaccurate if your car was replaced with the mesh that had the hood dented upward and the bumper breaking, since there was no collision even close to that area! This leads to the limitation of this approach. Developers using this work-around would have to spend LOTS of time creating LOTS of separate meshes, UVs, and Textures for the game object to act realistically. Developers would also have to worry about the specified area of impact to make the mesh replacement more realistic and physically correct! Not only that, but the same 3D models that represent the destruction of the car would become repetitive over time, unless you created a large number of them!

Thus the limitations of the approach to creating separate 3D models with varying amounts of damage would be:

• Time-consuming to create meshes

• Need to create lots of 3D meshes for different amounts of destruction, with UVs and Textures

• Managing the Transition between different meshes accurately upon collisions or deformation

• Unrealistic and Repetitive - if there aren't that many 3D models to replace the mesh with

That's a lot of information for today! Hope that was all clear! 

Sneak Peek of the Next Few Days of Content: Destruction

"Humans are creatures of creation... and destruction..." -Aaron Hernandez

Lately, I've been reading up on Destructible Environments in video games, and there is a LOT of content that I still have to read before I can write about it in depth! So over the next few days, I'll be covering this type of information.

So to keep things short for today, while I'm studying this topic, here is a sneak peek video of destruction in a game called Crackdown 3

Crackdown 3 is a new game that is supposedly coming out in 2019, and it seems that the developers are adding destructible environments for virtually every object in the game, including buildings! They actually had to use multiple servers to pack a lot of destructible objects into the game due to the massive computational load of mesh deformation. You can even shoot out pieces of a concrete wall and watch that piece fall and crack into a million pieces on the ground! How cool is that!

Here is a cool video from a few years ago of how you can literally destroy every single part of a building in Crackdown 3. I hope this still makes it to the actual game, as that would be a major step for future game development and even VR!

Vehicular Physics in Video Games

Hello everyone, 

For all you physics lovers out there in the world, today is all about Vehicle Physics in video games. I have been super busy today, so I'm going to make a very quick post about it! Now, I'm not going write up too much on the technical or mathematical nature of physics in video games. I'm mostly going to talk very briefly about the conceptual part and I'll post a thesis on a lot of simple (and complex) mathematical equations to consider when driving a car in the gaming world! However, that does NOT mean that I won't ever post about physics/mathematical equations on this blog. I definitely will post more on these topics later on as I learn them and as I take mathematical notes with the LaTeX document preparation system. 

Vehicle Physics is always an interesting topic to consider in lots of games, such as city-based games like Grand Theft Auto and Racing games like Need for Speed. However, you'll notice that a lot of major AAA games that AREN'T Racing related don't tend to implement too realistic of a vehicular physics-based system! Why? I think that the main reason a lot of major game companies aren't is because developers are focusing on creating other content that is way more important to the core game, such as the story, the environment, the weapons, or even just the overall gameplay experience. Nevertheless, vehicular physics can make games a whole lot more fun and intriguing! For example, suppose you've driving a huge truck with cargo in it and you're driving it along the road at a very high velocity. When you slam on the brakes, the cargo in the truck will probably move a bit towards the front of the truck and the truck should take a longer time to slow down to a complete stop than a small car. If video games neglect something as minor as this, it will make the physics system in the game seem wonky and unrealistic. That's why I like to think of Vehicular physics as a component of detail, and people tend to notice minor details like that!  

Here is a VERY interesting master project/thesis done by some unnamed author (at least I couldn't find it anywhere) about car physics. It discusses all sorts of physics equations related to drag, traction, engine torque, weight transfer, suspension, and even some collision detection and response and much much more! It also describes some of the physics pseudo-code,  which are human-readable notes on how the physics program should work.

https://nccastaff.bournemouth.ac.uk/jmacey/MastersProjects/MSc12/Srisuchat/Thesis.pdf

Here is also a cool Mad Max the game video on its car mechanics!

Ragdoll Physics in Video Games

I remember first becoming fascinated with physics when I went to Six Flags Great America back in 8th grade. I remember waiting in line for this one rotational cart ride with my one friend, and we began talking about how all these roller-coasters and rides supposedly "worked".  This one old man heard our conversation, turned around, looked us in the eye and screamed "You gotta use physics!" That was my starting point! 

Anyway, I am currently interested in getting some kind of degree in Physics at UW-Madison because I love to think of all the applications involved in video games and simulations! I am currently reading John Taylor's Classical Mechanics.

I discovered that many games rely on a Physics-based, computer animation technique called  Ragdoll Physics.

One important thing to mention before discussing more on physics is the idea of animation. More recent Game engines (from the late-1990's to present day) utilize a skeletal system for their characters, where the animators create, place, and link "bones" on their characters that can be posed and constrained. These bones are joined together in such a way that the animators can create animations by moving/rotating these bones individually while recording an animation. This mathematical process uses the kinematic equations to find the joint angles between interconnected segments (bones) and the pose/configuration among these bones; this is called "Inverse Kinematics." I haven't yet learned the mathematical formulations for inverse kinematics, although I will definitely touch up on this again in the future! It involves Jacobians!

Ragdoll Physics is a type of physics system that utilizes "Procedural Animations", which are real-time, generated animations of characters in a gaming world that are played when objects interact with their skeletal structure. For example, if the player gets hit by a ball, the player's character may animate (or respond) differently each time the ball is thrown at him/her. This is incredibly useful because it sometimes allows developers to eliminate tons of predefined animation sequences that are hard-coded into the game and that are often repeated again and again. Ragdoll physics offers more animation diversity!

Here is a Wikipedia article on Ragdoll physics if people are interested, or if you like Wikipedia. I love watching the videos/simulations that Wikipedia users provide, and this is definitely an interesting page. It links to other kinds of topics too.

https://en.wikipedia.org/wiki/Ragdoll_physics

Here is a short video on the history of Ragdoll Physics

Briefly on Ray Tracing and Real-Time Rendering

Ever since I wanted to create my own video game engine, I've always been keeping my eye on any sort of new gaming discoveries that have been made. I continually look at past articles on certain game engine techniques.

Lately, I've been studying some really complex mathematics behind Ray Tracing, which is a rendering technique that uses rays of light to determine object interactions and realistic reflections within the gaming world. It is STUNNING how realistic this rendering technique is! However, the only problem with Ray Tracing is that it requires a LOT of processor power to the point where it currently is not able to render in Real-Time on almost all computers. Movies are able to utilize this rendering technique because there are "rendering farms" that can render different scenes for hours and hours. However, video games update every fraction of a second, and thus cannot rely on mastering real-time rendering for all sorts of gaming computers anytime soon. 

Yet, I've read that Nvidia, a leading computing company that manufactures GPUs and specializes in graphics for gaming, has come out with a Ray Tracing library called RTX way back in March. Nvidia seems to be striving for real-time rendering in the distant future using this library! They also announced their largest GPU called the "Quadro GV100", which is supposedly $9,000!

There is so much to explain, and I will do my best to elaborate as I am learning this amazing topic! 

Here is a link to "How Nvidia’s RTX Real-Time Ray Tracing Works", which provides a really cool demo video for the upcoming game Metro: Exodus in 2019. I'll post the Metro video and a couple of video demos below too! 

How Nvidia's RTX Real-Time Ray Tracing Works

https://www.extremetech.com/extreme/266600-nvidias-rtx-promises-real-time-ray-tracing