For the last couple of weeks I've been working on my final project for my physically-based modeling and simulation course, which is going to be a real-time, interactive terrain modeling system using hydraulic erosion (more on that at a later date). Instead of using OpenGL like we have all semester I decided to delve into DirectX 10, since I most likely will be using DirectX out in industry and therefore need to start getting experienced with it. Yup, this is my first DirectX adventure, and what an adventure it's turning out to be.
I'm finding that good online DX10 resources are few and far between. Sure, there's MSDN that lists all the API functions and whatnot, but it doesn't really clearly tell you what they're used for or exactly how you would use them. Most of the documentation is fairly vague, and there aren't any code examples of everything in action except for a few basic tutorials that come with the SDK. For someone new to DirectX, the journey is frequently rough and slow-going. I guess it's time to find a good book on the subject.
As soon as I have something to show from my project I'll get it posted.
Friday, March 26, 2010
Wednesday, March 17, 2010
Constrained Particle Dynamics
For our second assignment in my physically-based modeling and simulation course we were given the task of implementing a particle system capable of imposing constraints upon the particles. An example of a constraint would be requiring two particles to always stay a fixed distance apart. The trick is getting the particles to obey physics while also obeying all constraints imposed upon them. How do we define the particles' behavior to accomplish this?
It turns out a good way to do this is through the use of constraint forces, which are directly-calculated forces that cancel out all illegal accelerations, thereby only allowing the particles to move in a way that maintains their constraints. When I say the forces are directly calculated I mean that the force calculations are done before the particles have violated their constraints, in effect never allowing them to do so. This is in contrast to the penalty method which applies restorative forces after the particles have already violated their constraints (such as in the collision response of the mass-spring system I did earlier).
There's an excellent reference on the internet by Andrew Witkin of Pixar that explains constrained particle dynamics and how to use them. Because his article is basically what I used to learn about the topic, I'm not going to give any kind of lengthy explanation about the math or implementation of the system, since I would essentially just be repeating what he's already said. And besides, I'm sure his explanations are better anyway. The article can be found here.
One aspect of Witkin's method that makes it ideal for interactive applications is the treatment of constraints as individual objects that can be inserted and deleted from the system as needed. Each constraint object is responsible for calculating and filling in its own portions of the required matrices. What this means is that you don't have to hard-code the linear system of equations that need to be solved, which allows for an interactive simulation that can add and remove particles, and their constraints, at will. If you have no idea what I'm talking about, then I refer you to the reference above. =)
The video below shows my implementation of Witkin's system, using 18 particles constrained to a ring. The top-most particle is constrained to remain in place, the bottom-most particle is constrained to remain on the ring, and every particle is constrained to remain a fixed distance from its neighbors. External forces are applied interactively through keyboard input. There's also no collision (by design), because the 3D-ness of everything is just meant as a visual aid to help "see" the constraints. And just like the first assignment, this too is written in C/C++ and OpenGL.
It turns out a good way to do this is through the use of constraint forces, which are directly-calculated forces that cancel out all illegal accelerations, thereby only allowing the particles to move in a way that maintains their constraints. When I say the forces are directly calculated I mean that the force calculations are done before the particles have violated their constraints, in effect never allowing them to do so. This is in contrast to the penalty method which applies restorative forces after the particles have already violated their constraints (such as in the collision response of the mass-spring system I did earlier).
There's an excellent reference on the internet by Andrew Witkin of Pixar that explains constrained particle dynamics and how to use them. Because his article is basically what I used to learn about the topic, I'm not going to give any kind of lengthy explanation about the math or implementation of the system, since I would essentially just be repeating what he's already said. And besides, I'm sure his explanations are better anyway. The article can be found here.
One aspect of Witkin's method that makes it ideal for interactive applications is the treatment of constraints as individual objects that can be inserted and deleted from the system as needed. Each constraint object is responsible for calculating and filling in its own portions of the required matrices. What this means is that you don't have to hard-code the linear system of equations that need to be solved, which allows for an interactive simulation that can add and remove particles, and their constraints, at will. If you have no idea what I'm talking about, then I refer you to the reference above. =)
The video below shows my implementation of Witkin's system, using 18 particles constrained to a ring. The top-most particle is constrained to remain in place, the bottom-most particle is constrained to remain on the ring, and every particle is constrained to remain a fixed distance from its neighbors. External forces are applied interactively through keyboard input. There's also no collision (by design), because the 3D-ness of everything is just meant as a visual aid to help "see" the constraints. And just like the first assignment, this too is written in C/C++ and OpenGL.
Tuesday, March 16, 2010
Deformable Objects Via 3D Mass-Spring Systems
This semester I'm taking a course on physically-based modeling and simulation, a topic that sounded interesting when I signed up for it but one that I didn't know too much about. So far it's turning out to be very interesting indeed, and challenging and fun too. I'd say it's the best course I've taken yet.
For our first assignment we had to simulate a deformable jello cube that moves around within a bounding box under an arbitrary non-uniform force field, bouncing off any plane it comes into contact with. The jello cube itself is modeled as a 3D mass-spring system: the cube is discretized into a grid of mass points that are all connected to their neighbors with springs. The springs are what maintain the cube's shape but at the same time allow jello-like deformity.
It turns out just having each mass point connect to each of its six direct neighbors isn't enough to maintain the cube's shape - the grid of points can shear while still allowing the springs to remain at rest, resulting in a collapsed (i.e. flattened) cube of jello. There are actually three different types of springs needed to keep the cube from losing its form:
1) structural springs (direct neighbor links, defines the shape of the cube)
2) shear springs (diagonal neighbor links, prevents shearing)
3) bend springs (direct 2nd-neighbor links, prevents folding)
Ok, that's not entirely true. The bend springs aren't strictly necessary for a cube shape because the other two types will keep the cube from folding over anyway. However, a 2D simulation such as cloth would need all three types (assuming you didn't want to allow the cloth to fold over on itself).
The cube in our assignment consists of 512 mass points in total (8x8x8) resulting in 6,220 springs in the system. In contrast, a system consisting of just 8 points (2x2x2) would have 28 springs. As you can see, the number of springs grows exponentially with the number of mass points. This can make finely-grained modeling of large objects using mass-spring systems not very feasible. The screenshot below shows just the surface points and connected structural springs of the jello cube.
The elastic forces exerted by the springs are found by using Hook's Law, F = -kx. In addition to these forces there also needs to be a damping force that always opposes the motion. Without any kind of damping the springs would oscillate indefinitely and eventually the simulation would fail. Damping forces are modeled similarly to elastic spring forces, except they depend on the velocity: F = -kv. Note that the value of k is different for damping than it is for springs. The two forces are added together to obtain a spring's overall force contribution.
Collision with a plane is handled via the penalty method. Once a mass point has been found to be colliding with the plane, an artificial collision spring is placed perpendicularly between the plane's surface and the mass point. This new spring will push/pull the mass point backwards and away from the colliding plane. As you might expect, collision springs have their own elasticity and damping coefficients, just like ordinary springs.
The final piece of the simulation is the external force field which causes the jello cube to move around within the bounding box. The field's resolution (i.e. the number of force points in the field) can be arbitrary, and the cube is constantly moving, so trilinear interpolation is used to find the exact force at each mass point.
So what does all of this add up to? Using Newton's 2nd Law, F = ma, the acceleration of each mass point can be calculated as follows:
Combining the equations together for all the mass points gives us a system of ODEs (ordinary differential equations), which can be solved numerically using integrators. Examples of such integrators are Euler, Runge-Kutta 2nd-order (RK2, a.k.a. midpoint method), and Runge-Kutta 4th-order (RK4). I won't go into how they work here; that's a topic unto itself. Deciding which integrator to use is usually a tradeoff between accuracy and computational cost. For example, the Euler method is computationally inexpensive but very inaccurate. Very small timesteps are needed to keep it stable which doesn't allow for fast simulations, so it's rarely used in practice. The Euler and RK4 methods were both implemented for the assignment.
The first video below clearly shows the deformations of the jello cube as it bounces off the walls. The second video is the simulation I turned in for the assignment. Different values for the spring and damping coefficients were used to achieve the different effects. And for those who are wondering, the simulation is writtin in C/C++ and OpenGL.
For our first assignment we had to simulate a deformable jello cube that moves around within a bounding box under an arbitrary non-uniform force field, bouncing off any plane it comes into contact with. The jello cube itself is modeled as a 3D mass-spring system: the cube is discretized into a grid of mass points that are all connected to their neighbors with springs. The springs are what maintain the cube's shape but at the same time allow jello-like deformity.
It turns out just having each mass point connect to each of its six direct neighbors isn't enough to maintain the cube's shape - the grid of points can shear while still allowing the springs to remain at rest, resulting in a collapsed (i.e. flattened) cube of jello. There are actually three different types of springs needed to keep the cube from losing its form:
1) structural springs (direct neighbor links, defines the shape of the cube)
2) shear springs (diagonal neighbor links, prevents shearing)
3) bend springs (direct 2nd-neighbor links, prevents folding)
Ok, that's not entirely true. The bend springs aren't strictly necessary for a cube shape because the other two types will keep the cube from folding over anyway. However, a 2D simulation such as cloth would need all three types (assuming you didn't want to allow the cloth to fold over on itself).
The cube in our assignment consists of 512 mass points in total (8x8x8) resulting in 6,220 springs in the system. In contrast, a system consisting of just 8 points (2x2x2) would have 28 springs. As you can see, the number of springs grows exponentially with the number of mass points. This can make finely-grained modeling of large objects using mass-spring systems not very feasible. The screenshot below shows just the surface points and connected structural springs of the jello cube.
The elastic forces exerted by the springs are found by using Hook's Law, F = -kx. In addition to these forces there also needs to be a damping force that always opposes the motion. Without any kind of damping the springs would oscillate indefinitely and eventually the simulation would fail. Damping forces are modeled similarly to elastic spring forces, except they depend on the velocity: F = -kv. Note that the value of k is different for damping than it is for springs. The two forces are added together to obtain a spring's overall force contribution.
Collision with a plane is handled via the penalty method. Once a mass point has been found to be colliding with the plane, an artificial collision spring is placed perpendicularly between the plane's surface and the mass point. This new spring will push/pull the mass point backwards and away from the colliding plane. As you might expect, collision springs have their own elasticity and damping coefficients, just like ordinary springs.
The final piece of the simulation is the external force field which causes the jello cube to move around within the bounding box. The field's resolution (i.e. the number of force points in the field) can be arbitrary, and the cube is constantly moving, so trilinear interpolation is used to find the exact force at each mass point.
So what does all of this add up to? Using Newton's 2nd Law, F = ma, the acceleration of each mass point can be calculated as follows:
Combining the equations together for all the mass points gives us a system of ODEs (ordinary differential equations), which can be solved numerically using integrators. Examples of such integrators are Euler, Runge-Kutta 2nd-order (RK2, a.k.a. midpoint method), and Runge-Kutta 4th-order (RK4). I won't go into how they work here; that's a topic unto itself. Deciding which integrator to use is usually a tradeoff between accuracy and computational cost. For example, the Euler method is computationally inexpensive but very inaccurate. Very small timesteps are needed to keep it stable which doesn't allow for fast simulations, so it's rarely used in practice. The Euler and RK4 methods were both implemented for the assignment.
The first video below clearly shows the deformations of the jello cube as it bounces off the walls. The second video is the simulation I turned in for the assignment. Different values for the spring and damping coefficients were used to achieve the different effects. And for those who are wondering, the simulation is writtin in C/C++ and OpenGL.
GPU's Back In The Game!
After being told that my replacement GPU would take about a week to arrive, imagine my surprise when it showed up today, only two days after I called the company about it. Now that's service!
But even after just two days of looking at 1024x768 resolution with graphical corruption, having my screen returned to normal looked strange at first. I think I was actually getting used to my sub-par visuals. Scary.
But even after just two days of looking at 1024x768 resolution with graphical corruption, having my screen returned to normal looked strange at first. I think I was actually getting used to my sub-par visuals. Scary.
Sunday, March 14, 2010
GPU FTL
Efforts to post my projects have been put on hold for at least a week, thanks to my GeForce 8800 GTX crapping out on me. Most of the projects from here on out require a GPU, and without one of those I can't get any screenshots or videos. Annoying to say the least.
Luckily the card is still under warranty, so a new replacement is on its way for free. But not being able to work from home on any of my current school projects requiring a GPU is definitely frustrating, and will inevitably lead to some long nights in the near future in order to make up for lost time. Thanks, GPU.
Luckily the card is still under warranty, so a new replacement is on its way for free. But not being able to work from home on any of my current school projects requiring a GPU is definitely frustrating, and will inevitably lead to some long nights in the near future in order to make up for lost time. Thanks, GPU.
Friday, March 12, 2010
The Best 2D Space Shooter Ever Made...
...was of course Gradius 3. Some may argue with that statement, but that game gave me countless hours of enjoyment on the Super NES. Even today I still have fun playing it. So when a fellow hobbyist game developer clued me in to the world of homebrew GameBoy Advance games, I pretty much knew immediately what game I'd love to make for it. Doing Gradius 3 for the GBA would pose few problems, if any, since the GBA is essentially a hand-held SNES.
Creating a GBA game for my second dev experience seemed like a good fit because I would be working in a console environment, but without the scariness of jumping head-first into full-blown 3D. It turned out to be a very fun project, I thoroughly enjoyed having to design for a limited-memory and limited-capability system (getting all five of the parallaxed starfields to operate within just one of the four hardware tilemap layers was quite a challenge in itself).
The video below is the demo game I put together. Sadly I stopped working on it before it could be considered a "complete" game - it was reaching a point of diminished returns for my time and effort, so I thought it would be better to move on to something else. The entire thing is written in C and was tested on the VisualBoy Advance GBA emulator.
The video is a bit choppy (to keep the file size down) but the game runs at a smooth 60 FPS. Well, technically it runs at 59.73 FPS (2^24 clock speed with a full screen refresh taking exactly 280,896 cycles), but who's counting...
Creating a GBA game for my second dev experience seemed like a good fit because I would be working in a console environment, but without the scariness of jumping head-first into full-blown 3D. It turned out to be a very fun project, I thoroughly enjoyed having to design for a limited-memory and limited-capability system (getting all five of the parallaxed starfields to operate within just one of the four hardware tilemap layers was quite a challenge in itself).
The video below is the demo game I put together. Sadly I stopped working on it before it could be considered a "complete" game - it was reaching a point of diminished returns for my time and effort, so I thought it would be better to move on to something else. The entire thing is written in C and was tested on the VisualBoy Advance GBA emulator.
The video is a bit choppy (to keep the file size down) but the game runs at a smooth 60 FPS. Well, technically it runs at 59.73 FPS (2^24 clock speed with a full screen refresh taking exactly 280,896 cycles), but who's counting...
Thursday, March 11, 2010
Good ol' Tetris
Back when I was first becoming interested in game development a few years ago, I didn't know the first thing about making a game, even a simple one. I knew how to write code, but that was it. So after some searching around on the internet on "how to make a video game" it seemed the popular answer was to start off by making some sort of variant of either Tetris or Breakout. I was much more familiar with Tetris, having played the crap out of that game on the original GameBoy when I was a kid, so I went with that.
I learned just enough Windows programming to make it run on a PC, and wrote the entire thing in C++. The video below shows a quick demo of the final version.
What you don't see in the video is the variable grid size and additional block shapes I added. The initial launch window that appears when you run the game lets you select the size of the grid to play in, and lets you select what kind of block shapes to use. For instance, the standard grid size is 10x18, but on my current monitor I can have a grid size of up to 64x42 - pretty ridiculous. Playing with a huge grid area and up to 87 different block shapes is amuzing, but the classic version is truly the most fun.
I learned just enough Windows programming to make it run on a PC, and wrote the entire thing in C++. The video below shows a quick demo of the final version.
What you don't see in the video is the variable grid size and additional block shapes I added. The initial launch window that appears when you run the game lets you select the size of the grid to play in, and lets you select what kind of block shapes to use. For instance, the standard grid size is 10x18, but on my current monitor I can have a grid size of up to 64x42 - pretty ridiculous. Playing with a huge grid area and up to 87 different block shapes is amuzing, but the classic version is truly the most fun.
Tuesday, March 9, 2010
And so it begins...
As I'm sure many a blog start off, I will also start off by saying "This is my first experience with blogs." I'm not into the whole social networking craze, so this is also my first real experience with putting bits and pieces of my personality and life out for everyone to read about. However, I think it's important that I have a place to showcase some of the work I've been doing and will do in the future, given that I'm currently a grad student who will graduate in a little over a year, at which point I will need to have found that ever-important job. Throwing it all into a blog seems like a perfectly fine choice to me, and hopefully will somewhat demonstrate what I'm capable of. That's not the only reason for this blog, but it is a piece of the puzzle.
My first few posts will most likely be about past projects, with the current stuff to follow. Another good reason for me to start this blog is it will help me remember everything that I've worked on, and any interesting tidbits I learned along the way. I look forward to taking fond (and likely horrid, too) trips down coder memory lane.
My first few posts will most likely be about past projects, with the current stuff to follow. Another good reason for me to start this blog is it will help me remember everything that I've worked on, and any interesting tidbits I learned along the way. I look forward to taking fond (and likely horrid, too) trips down coder memory lane.
Subscribe to:
Posts (Atom)
