Sunday, March 16, 2014

Physics Force Registry

This steps through how to set up the basic elements of a force registry system. This kind of system creates and manages forces and makes it easy to implement different kinds of physics behaviors such as acceleration due to gravity, planetary orbits, or spring motion simply by creating a variety of simple force-generating behaviors and applying them to basic units. To create this system I used OpenGL (freeglut) and my own Vector3 class with basic functionality. This system does not handle collision, but would not be difficult to integrate with a collision system.

The most basic element of this system is the ForceGenerator. This is a virtual base class that should be extended for each specific type of force needed. It is registered with a unit and is used to calculate the correct force and apply that force to the unit. The base class is very simple, but different members may be needed for more complex forces.

ForceGenerator.h

class ForceGenerator
{
    float Duration;
    virtual void updateForce(Unit* unit)=0;
}


updateForce(Unit* unit) is where the force is calculated and applied to unit and Duration indicates an amount of time this force should be applied. If you want a force to be applied forever setting duration to FLT_MAX and not decrementing the time if it is set to this would allow the ForceGenerator to never be removed from the registry.

One use for a ForceGenerator would be to create simple spring motion. With a simple ForceGenerator you can get fairly complex and convincing behavior with very little code:

Spring.h

class Spring:public ForceGenerator
{
    float RestLength;
    float SpringConstant;
    Unit* BaseUnit;

    Spring(Unit* base,float springConstant=1,float restLength=0);
    void updateForce(Unit* unit);
}


Spring.cpp

Spring::Spring(Unit* base,float springConstant,float restLength)
{
    BaseUnit=base;
    SpringConstant=springConstant;
    RestLength=restLenght;

    Duration=FLT_MAX; //this force will stay forever
}

void Spring::updateForce(Unit* unit)
{
    Vector3 dir = BaseUnit->Position - unit->Position;
     //get the direction of the force to be applied

    float dist = dir.Magnitude();
     //get the distance between unit and BaseUnit

    float offset = RestLength - dist;
     //get the offset from the rest length for determining the magnitude of the force

    dir.Normalize();
    Vector3 force = dir * (-SpringConstant * offset);
     //calculate the spring force

    unit->addForce(force);
}


By registering this Spring with a Unit you will get anchored spring motion with the anchor being the BaseUnit. If you would like the BaseUnit to be affected by the spring as well, you would register another Spring force with the BaseUnit and the BaseUnit of the Spring set to the Unit that the last Spring was registered with.

You can view my code for basic gravity here ( Gravity.h  Gravity.cpp )
or for planetary gravity here ( PlanetGravity.h  PlanetGravity.cpp ).

This ForceGenerator is queued for processing with a Unit pointer with a ForceRegistration which is a simple struct:

ForceRegistration.h

struct ForceRegistration
{
    Unit* unit;
    ForceGenerator* force;
}


The unit in the ForceRegistration is the one that will be passed to force->updateForce(). The Unit class at its most basic needs to contain the following:

Unit.h

class Unit
{
    Vector3 Position;
    Vector3 Forces; //Force accumulator
    Vector3 Velocity;

    float Mass;
    float InverseMass;
    float Radius;

    void update();
    void draw();
    void addForce(Vector3 force);
}


This Unit class is specifically for spherical units for simplicity, but Radius could be replaced with some kind of dimensions variable for other shapes. Also, I am storing both the mass and the inverse mass so that they do not have to be calculated each frame.

Now that we have each of the basic components involved in the force registry system we need to create the actual ForceRegistry. The ForceRegistry is entirely just a ForceRegistration holder and updater.

ForceRegistry.h

class ForceRegistry
{
    vector<forceregistration> ActiveForces;

    void add(ForceRegistration* force);
    void clear();
    void remove(int index);
    void updateForces();
}


ForceRegistry.cpp

void ForceRegistry::add(ForceRegistration* force)
{
    ActiveForces.push_back(force);
}

void ForceRegistry::clear()
{
    for(unsigned int i=0;i<ActiveForces.size();i++)
    {
        delete ActiveForces[i];
    }
    ActiveForces.clear();
}

void ForceRegistry::remove(int index)
{
    delete ActiveForces[index];
    ActiveForces.erase(ActiveForces.begin()+index);
}

void ForceRegistry::updateForces()
{
    for(unsigned int i=0;i<ActiveForces.size();i++)
    {
         //remove ForceRegistrations that have run their course
        if(ActiveForces[i]->Unit->Duration <= 0)
        {
            remove(i);
            i--;
            continue;
        }

         //update forces
        ActiveForces[i]->Force->updateForce(ActiveForces[i]->Unit);

         //decrement force duration
        if(ActiveForces[i]->Unit->Duration &lt FLT_MAX)
            ActiveForces[i]->Unit->Duration -= DeltaTime;
    }
}


The last step is to make sure that the units process and apply their accumulated forces correctly when updated. To do this you apply the velocity to the position, calculate acceleration from the accumulated forces, apply the acceleration to the velocity and then clear out the accumulated forces.

Unit.cpp

void Unit::update();
{
     //apply velocity
    Position += Velocity * DeltaTime;

     //calculate acceleration
    Vector3 acc = Forces * InverseMass;

     //apply acceleration
    Velocity += acc * DeltaTime;

     //clear force accumulator
    Forces = Vector3(0,0,0);
}



Now all that's left to do is register a ForceGenerator with a Unit.


//create the anchor and unit
Unit* anchor=new Unit();; anchor->Position=Vector3(0,0,0); anchor->Radius=1;
Unit* unit=new Unit();; unit->Position=Vector3(3,6,9); anchor->Radius=1;

//create the spring force and a force registration
Spring* spring=new Spring(anchor,1.2f,5.0f);
ForceRegistration* reg=new ForceRegistration(unit,spring);

//add the ForceRegistration to a previously made ForceRegistry
forceRegistry.add(reg);


This will result in an anchored spring object.
You can view my whole system code here.

Thursday, March 13, 2014

Self-Regenerating Destructible Objects

Destructible objects and terrain are pretty much awesome, so I figured I'd try implementing it myself (being able to program is fantastic). One thing I really wanted to focus on was making objects regenerate themselves once they had been destroyed. The main problem with destructible assets in games is that at some point everything is destroyed and one of the coolest features is eliminated; by having the assets gradually regenerate themselves this problem is avoided.

After looking into it a bit I decided that a voxel system would be the best way to accomplish this. A voxel is basically a particle with volume. By packing them together you can form a whole object or terrain whose individual voxels can be manipulated separately allowing for sections of it to be, for example, destroyed. Above is an example from my final product. The whole object is a box, but because it is made up of voxels, the upper right section can be easily removed independently.

The basic implementation was not even all that difficult. The first step for me was to set up some of the basic structures I would need. The two main ones were the Voxel which would hold information about itself and the VoxelUnit which would store and manage all the voxels contained in it. The VoxelUnit basically acts as a box that fills itself up with voxels and then makes decisions about activating and destroying each one; having this structure allows for there to be separate voxel objects that can be manipulated independently.

For this tech demo I used OpenGL and my own Vector3 class which holds three floats (x, y, z) and has basic vector math functionality.

You can view my code here.

Because the VoxelUnit handles the collision and display of each of its voxels, the Voxel itself is pretty simple.


struct Voxel
{
    Depth depth;
    float regenTimer;
};


The regenTimer is pretty obvious. To avoid instantaneous regeneration, each Voxel keeps track of how long it has been waiting to regenerate so that they can be regenerated gradually after a set amount of time.
The depth variable is a little more complex. This is used as a kind of depth identity; it is an integer defined by the following Depth enum.


enum Depth{ EMPTY=-3, DESTROYED, BORDER, SURFACE, CENTER };


EMPTY indicates a voxel that is not displayed or interacted with and will never regenerate; this allows for shapes other than a cube. In this system every VoxelUnit is made up of a box full of voxels, but by making some empty, different voxel shapes can be achieved.
DESTROYED voxels are like empty voxels, but they can be regenerated and border voxels are destroyed voxels that are adjacent to surface voxels; the VoxelUnit increments the regenTimer of these.
SURFACE and CENTER voxels are filled, but only surface voxels are rendered. Separating them also makes it convenient if you were to check surface collisions later.
EMPTY is set to -3 so that SURFACE is 0. By setting it up this way and putting the Depth values in order, you can easily check if the voxel is active by checking if its depth is greater than or equal to zero.

The VoxelUnit is basically just a Voxel manager:


class VoxelUnit
{
    ///// variables
    Vector3 Position;
    Vector3 Color;
    Vector3 Dimensions;
    Vector3 VoxelDimensions;
      //dimensions in number of voxels
    float VoxelSize;
      //the size of each side of each voxel
    Voxel*** Voxels
      //3D array to store the voxels

    ///// functions
    void update();
    void draw();

    void reassignDepth();
      //checks/resets the depth value for every Voxel
    Voxel* getAdjacent(Vector3 index);
      //returns an array of voxels adjacent to the one at index
    bool checkCollision(Vector3 c, float r);
      //check collision with a sphere at center c and radius r
};


I'll describe what each of these functions is responsible for later on, but first we need to populate our voxel array.
The first thing you need to do is determine is the voxel dimensions based on the desired dimensions of the box and the desired voxel size.

VoxelUnit.cpp

VoxelDimensions=Dimensions/VoxelSize;
VoxelDimensions=Vector3((int)VoxelDimensions.x,
                        (int)VoxelDimensions.y,
                        (int)VoxelDimensions.z);


It's important to make sure that the voxel dimensions are integers -- you don't want partial voxels.
To populate the array, you simply loop through and assign the voxels at the desired depth value.

VoxelUnit.cpp

Voxels=new Voxel**[(int)VoxelDimensions.x];
for(int x=0;x<VoxelDimensions.x;x++)
{
    Voxels[x]=new Voxel*[(int)VoxelDimensions.y];
    for(int y=0;y<VoxelDimensions.y;y++)
    {
        Voxels[x][y]=new Voxel[(int)VoxelDimensions.z];
        for(int z=0;z<VoxelDimensions.z;z++)
        {
            Voxels[x][y][z].depth=CENTER;
            Voxels[x][y][z].regenTimer=0;
            //for generating a different shape:
            //if(i>10 && i<VoxelDimensions.x-11
            //    && j>10 && j<VoxelDimensions.y-11)
            //    Voxels[x][y][z].depth=EMPTY;
        }
    }
}


Assigning all the depth values to CENTER will result in a completely filled in box; you can get creative with generating interesting shapes though by setting the depth value of certain voxels to EMPTY (they will remain empty). Including the commented section in the code above will result in a box with a tunnel through the center of it, for example.

Throughout most of these functions, most of the actual logic will happen inside the inner-most loop of the nested loop structure because it allows access to each individual voxel.

The next key element of the VoxelUnit class is the reassignDepth function. This function is used to go through and make sure every voxel has the correct depth value after there is any change to the VoxelUnit. An optimal system might disperse this function and handle reassignment more locally depending on specific situations, but for the sake of getting things working, going through and reassigning the depth after any change ensures that reassignment will always be consistent and you can avoid a lot of edge cases. The depth of each voxel is mostly determined by the depths of the voxels surrounding it; this is where our getAdjacent function is primarily utilized as well.

Instead of writing out the nested loop to access each element, assume the following code is surrounded by such a loop and x, y, and z are the index values of the voxel for each array as it was above.

VoxelUnit.cpp

////// void reassignDepth() //////
//for each Voxel in Voxels:

Vector3 index(x,y,z);
 //get an array of adjacent voxels
Voxel* adj=getAdjacent(index);


 //first we handle the voxels that are active (surface or center)
if(Voxels[x][y][z].depth>=0)
{
      //check to see if any of the adjacent voxels are inactive or "outside"
    bool outsidePresent=false;
    for(int i=0;i<6;i++)
    {
        if(adj[i].depth<0) //values less than 0 are inactive
            outsidePresent=true;
    }
    if(outsidePresent)    //if next to an inactive voxel
        Voxels[x][y][z].depth=SURFACE;
    else                  //if all surrounding voxels are active
    Voxels[x][y][z].depth=CENTER;
}


 //next we handle inactive voxels (border or destroyed)
else if(Voxels[x][y][z].depth!=EMPTY)
{
     //check to see if any of the adjacent voxels are active
    bool objectPresent=false;
    for(int i=0;i<6;i++)
    {
        if(adj[i].depth>=0) //values 0 and higher are active
            objectPresent=true;
    }
    if(objectPresent)    //if next to an active voxel
        Voxels[x][y][z].depth=BORDER;
    else                 //if all surrounding voxels are inactive
        Voxels[x][y][z].depth=DESTROYED;
}


All that getAdjacent(Vector3 index) does is return an array of the six voxels with one greater and one less index value for each dimension. To ensure that even edge voxels (index value of 0) have six adjacent voxels, I first populated the array with voxels that had a depth of EMPTY and reassigned them if the voxel actually existed.
Calling reassignDepth() after instantiating a new voxel array will sort out what is a surface, center, border, etc voxel so that you don't have to worry about that while instantiating.

The update() function is really pretty simple. It is mostly responsible for incrementing the border voxels' regenTimer and restoring the voxels that have waited the necessary time to regenerate.

VoxelUnit.cpp

////// void update() //////
//for each Voxel in Voxels:

if(mVoxels[x][y][z].depth==BORDER)
{
    Voxels[x][y][z].regenTimer+=DeltaTime; //add the time passed to the Voxel's timer
    if(Voxels[x][y][z].regenTimer>=RegenTime)
    { //if the timer has reached the required wait time, fill the voxel
        Voxels[x][y][z].depth=CENTER;
        Voxels[x][y][z].regenTimer=0;
        shouldReassign=true; //a boolean to keep track of if anything changes
    }
}

//if shouldReassign=true after each voxel is checked, call reassignDepth()


The next step is to draw the VoxelUnit. The most important thing involved with this is calculating each SURFACE voxel's position because the Voxel in my system does not hold its own position. Maybe it should, but it's easy enough to calculate, so I'm just going to stick with that.

VoxelUnit.cpp

////// void draw() //////
//for each Voxel in Voxels:

if(mVoxels[x][y][z].depth==SURFACE) //only draw surface voxels
{
     //find the position of the specific voxel
    Vector3 pos=Position-(VoxelDimensions*VoxelSize/2);
    Vector3 index(x,y,z);
    pos+=index*VoxelSize;

     //the following is for the fun rainbow coloration in my examples, based on a root Color
    Vector3 color=(Vector3(1,1,1)-Color);
    color.x*=index.x/VoxelDimensions.x;
    color.y*=index.y/VoxelsDimensions.y;
    color.z*=index.z/VoxelsDimensions.z;

    //Draw your voxel cube at pos with color
}


All of this gives you a VoxelUnit that draws and regenerates itself, now all that's left to do is make it destructible. In my tech demo I only handle destructive sphere collision, but it would not be difficult to check collisions with other shapes as well. Basically you first determine if your destructive area collides with the bounding box of the VoxelUnit at all. If it does, loop through each of the voxels and, if the voxel is active (voxel.depth>=0), check to see if it collides with the destructive area. The depth of each voxel that collides should be set to DESTROYED and, unless no voxels were destroyed, reassignDepth() should be called.

The end result should be a destructible voxel object that regenerates itself over time, like so:


Or, if the VoxelUnit is not a solid box:




As you may have noticed in that clip, I set it so that you could change the destruction radius and the regeneration speed. It's also fun to play around with VoxelSize. The VoxelUnit in the video above has 90,000 voxels (as determined by a decreased VoxelSize), but you can get some pretty cool result with much fewer as well. Obviously, though, more voxels yields much smoother results; unfortunately this leads to massive frame rate hits as well.

720 voxels:


720,000 voxels:





Another cool thing I was able to accomplish with minimal additional effort in this system was the ability to place objects in the space without the VoxelUnit regrowing through it. This seemed like a good thing to implement on the premise of increased user immersion; if the player wanted to build on or place an object within a destroyed area, the voxel object or environment should not hinder that because of its regrowing.

By placing permanent spheres and applying destructive sphere collision every frame, the VoxelUnit will regenerate around the object, but will not regrow through it.

I added the ability to remove all of the permanent spheres, and it worked beautifully:




The next step for me in this project would be to get non-destructive collision working, so that these objects could be used as terrain or interacted with in ways other than being destroyed. Another feature I would love to add to this demo would be the ability to load in and "voxelize" custom models so that any object could be turned into a self-regenerating, destructible object. I'll post an update here when I accomplish these things!

Update: I can now voxelize models!