Upcoming Events
Unite 2010
11/10 - 11/12 @ Montréal, Canada

GDC China
12/5 - 12/7 @ Shanghai, China

Asia Game Show 2010
12/24 - 12/27  

GDC 2011
2/28 - 3/4 @ San Francisco, CA

More events...
Quick Stats
67 people currently visiting GDNet.
2406 articles in the reference section.

Help us fight cancer!
Join SETI Team GDNet!
Link to us Events 4 Gamers
Intel sponsors gamedev.net search:

Contents
 Case study
 Hyperion SDK
 Optimizations

 Printable version
 Discuss this article
 in the forums


The Series
 Part 1
 Part 2
 Part 3 (coming soon)

Deep look into the Hyperion SDK

Before going further, you can download sources and binaries of the project at the following address http://sourceforge.net/projects/ephydryne/. Documentation about the SDK and client applications are also available on the website.

The SDK provides a set of components called "Ephydryne components" which are the backbone of the project. The best way to learn how to use these components is to study the source code of the two client applications, HypDev and HypVisual.

The code developed in this project could not be considered completely achieved. The project is intended to be a starting point to the developers wanting to set up their own solutions. I hope that I have paved the way and shown pitfalls that should be avoided. This project is also intended to prove that this FEM adaptation is suitable for video games.

HypDev

HypDev is a console application used to calculate linear relations between displacements of rigid bodies and applied forces. Consequently, its goals are to find the matrix K'-1r and to save it in a file. This application is very light. It defines the CDevMesh class which wraps functionalities of the Ephydryne components.

class CDevMesh
{
public:
    CDevMesh(std::ostream& );
    ~CDevMesh();
    void CreateMesh();

    void Generation(const t_real& , const t_real& ,const t_real& ,
                    const int& ,const int& ,const int& );
    void SetDOF(const t_real& ,const t_real& ,const t_real& ,
                bool ,bool ,bool ,bool ,bool ,bool );
    void Construct();

    void ShowMesh(const std::string& );
    void SaveMesh(const std::string& );
    void SaveDisplayFile(const std::string& );

    void SetForce(const t_real& ,const t_real& ,const t_real& ,bool ,
                  bool ,bool ,const t_real& ,const t_real& ,const t_real& );
    void Solve();

private:
    //interfaces pointing to the same component
    hyp_ker::IPtrUnknown m_spUnknownMesh;
    hyp_fem::t_spGeometricBase m_spBaseMesh;
    hyp_fem::t_spGeometricObject m_spObjectMesh;
    hyp_fem::t_spFEOMesh m_spMeshMesh;

    std::ostream& m_Stream; //reference to stdio or to the log file
};

We are going to use the example studied in the previous part, that is, the cube. In order to obtain accurate results, meshing density will be multiplied by two. Consequently, the cube will not be divided into eight elements but into 64 elements. To obtain the matrix relation, you could write our own code or use HypDev through its command line. The source code is written below:

CDevMesh mesh(std::cout);                            //line 1
mesh.CreateMesh();                                   //line 2
mesh.Generation(2,2,2,4,4,4);                        //line 3
mesh.SetDOF(0,0,0,false,false,true,true,true,true);  //line 4
mesh.Construct();                                    //line 5
mesh.SaveMesh("cube.hyp");                           //line 6
mesh.SetForce(0,0,2,false,false,true,0,0,10000);     //line 7
mesh.Solve();                                        //line 8
mesh.ShowMesh("cube.txt");                           //line 9
mesh.SaveDisplayFile("cube.x");                      //line 10

The first step [line 2] is to create the CFEOMesh component. This component provides the solid description regarding geometry, associated materials, nodes, finite elements and boundary conditions.

void CDevMesh::CreateMesh() {
    m_spUnknownMesh.CreateInstance(hyp_fem::CLSID_hypCFEOMesh,0);
    m_spMeshMesh=m_spObjectMesh=m_spBaseMesh=m_spUnknownMesh;
}

The second step [line 3] is to create the nodes, the elements and the sides associated to the solid. The creation of the sides are disconnected from the FEM computation but are used to display the solid. Because the Ephydryne components do not know how to mesh the solid automatically, the programmer has to write his own procedure.

Parameter Description
a Dimension of the cube along the x-axis
b Dimension of the cube along the y-axis
c Dimension of the cube along the z-axis
d_a Number of elements along the x-axis
d_b Number of elements along the y-axis
d_c Number of elements along the z-axis

void CDevMesh::Generation(const t_real& a,const t_real& b,const t_real& c,
                          const int& d_a,const int& d_b,const int& d_c)
{
 hyp::t_label i=0;
 hyp::t_label_enum e;
 hyp::t_real xi,yi,zi;
 hyp_fem::IGeometricVertex* p_vertex=0;

 for(xi=0;xi<=a;xi+=a/d_a) {
  for(yi=0;yi<=b;yi+=b/d_b) {
   for(zi=0;zi<=c;zi+=c/d_c) {
    m_spObjectMesh->CreateVertex(i,xi,yi,zi);    //creation of nodes
    i++;
   }
  }
 }

i=0;
for(xi=0;xi<a;xi+=a/d_a) {
 for(yi=0;yi<b;yi+=b/d_b) {
  for(zi=0;zi<c;zi+=c/d_c) {
   //we have to respect the local numerotation of the element
   p_vertex=m_spBaseMesh->GetVertex(xi,yi,zi);
   e.push_back(m_spBaseMesh->GetLabel(p_vertex));

   p_vertex=m_spBaseMesh->GetVertex(xi+a/d_a,yi,zi);
   e.push_back(m_spBaseMesh->GetLabel(p_vertex));

   p_vertex=m_spBaseMesh->GetVertex(xi+a/d_a,yi+b/d_b,zi);
   e.push_back(m_spBaseMesh->GetLabel(p_vertex));

   p_vertex=m_spBaseMesh->GetVertex(xi,yi+b/d_b,zi);
   e.push_back(m_spBaseMesh->GetLabel(p_vertex));

   p_vertex=m_spBaseMesh->GetVertex(xi,yi,zi+c/d_c);
   e.push_back(m_spBaseMesh->GetLabel(p_vertex));

   p_vertex=m_spBaseMesh->GetVertex(xi+a/d_a,yi,zi+c/d_c);
   e.push_back(m_spBaseMesh->GetLabel(p_vertex));

   p_vertex=m_spBaseMesh->GetVertex(xi+a/d_a,yi+b/d_b,zi+c/d_c);
   e.push_back(m_spBaseMesh->GetLabel(p_vertex));

   p_vertex=m_spBaseMesh->GetVertex(xi,yi+b/d_b,zi+c/d_c);
   e.push_back(m_spBaseMesh->GetLabel(p_vertex));

   m_spMeshMesh->CreateElement(i,e);    //creation of the element
   e.clear();
   i++;
  }
 }
}

i=0;
for(xi=0;xi<a;xi+=a/d_a) {
 for(zi=0;zi<c;zi+=c/d_c) {
  for(yi=0;yi<=b;yi+=b) {
   //a side is constitued by three nodes.
   //Respect orientation of the sides in order to display them correctly
   p_vertex=m_spBaseMesh->GetVertex(xi,yi,zi);
   e.push_back(m_spBaseMesh->GetLabel(p_vertex));
   p_vertex=m_spBaseMesh->GetVertex(xi+a/d_a,yi,zi);
   e.push_back(m_spBaseMesh->GetLabel(p_vertex));
   p_vertex=m_spBaseMesh->GetVertex(xi+a/d_a,yi,zi+c/d_c);
   e.push_back(m_spBaseMesh->GetLabel(p_vertex));

   if(yi==b) InvertEnum(e);
   m_spObjectMesh->CreateSide(i,e);
   e.clear();i++;

   e.push_back(m_spBaseMesh->GetLabel(p_vertex));
   p_vertex=m_spBaseMesh->GetVertex(xi,yi,zi+c/d_c);
   e.push_back(m_spBaseMesh->GetLabel(p_vertex));
   p_vertex=m_spBaseMesh->GetVertex(xi,yi,zi);
   e.push_back(m_spBaseMesh->GetLabel(p_vertex));

   if(yi==b) InvertEnum(e);
   m_spObjectMesh->CreateSide(i,e);
   e.clear();i++;
  }
 }
}

//we do two other slightly different operations for the four other faces of the cube 

}

In summary, we have constructed 125 nodes, 64 elements and 192 sides. If you use cubic elements as Lego bricks through this API, you can construct more sophisticated solids such as bridges, houses. Notice that we do not specify the property of the material used. In fact, CFEOMesh provides a default material.

  Elastic modulus (E) [Pa] Poisson's ratio (s) [dimensionless]
Default material 100 000 0,2

It turns out that the value of the elastic modulus is not so important because the global matrix as well as the vector U is proportionate to E. Keep in mind that proportions of deformations are more important than values of deformations. Actually when elastic deformations are studied with normal loading conditions, these deformations are invisible by direct observation. For example, bricks of your house are slightly deformed by their own weight and by bricks above them, but measuring this phenomenon with naked eyes is impossible. However, when results are displayed, FEM software applications amplify deformations by multiplying them by a scalar called "coefficient of visualization". HypVisual, the other client application of the project, implements this feature. Consequently, as the maximum amplitude is defined indirectly by this coefficient of visualization, quality of the results depends on the accuracy of the deformation proportions and not on the accuracy of the deformation itself.

The third step [line 4] is to define the boundary conditions of the cube, which is fixed at its base.

Parameter Description
px If bx is true, DOF are applied on nodes in the plan which has x = px for equation
py If by is true, DOF are applied on nodes in the plan which has y = py for equation
pz If bz is true, DOF are applied on nodes in the plan which has z = pz for equation
bx Select the x plan
by Select the y plan
bz Select the z plan
dx Fix the DOF of the selected nodes along the x-axis
dy Fix the DOF of the selected nodes along the y-axis
dz Fix the DOF of the selected nodes along the z-axis

void CDevMesh::SetDOF(const t_real& px,const t_real& py,const t_real& pz,
                      bool bx,bool by,bool bz, bool dx,bool dy,bool dz)
{
    m_spMeshMesh->FixDOF(px,py,pz,bx,by,bz,dx,dy,dz);
}

The hypotheses are now defined. The computation of matrix relations can be carried out [line 5].

void CDevMesh::Construct()
{
    m_Stream<<"Construct Global Matrix...\n";
    m_spMeshMesh->ConstructGlobalMatrix();
    m_Stream<<"Construct Boundary Matrix...\n";
    m_spMeshMesh->ConstructBoundaryMatrix();
    m_Stream<<"Inverse Boundary Matrix...\n";
    m_spMeshMesh->InverseBoundaryMatrix();
    m_Stream<<"Construct Reduce Matrix...\n";
    m_spMeshMesh->ConstructVisibleMatrix();
}

The names of functions are self-explanatory. Firstly, we construct the global matrix, which has 375 rows and 375 columns. After using the boundary conditions, we obtain the boundary matrix K' which has 300 rows and columns. The inversion of the matrix K'-1 is done. Moreover, some nodes of the cube will be never seen by players, so we apply the render mask simplification. We now obtain the matrix K'-1r which is made up by 219 rows and 300 columns.

Saving the matrix K'-1r is the last operation [line 6].

void CDevMesh::SaveMesh(const std::string& path)
{
    m_Stream<<"Save Mesh in "<<path<<"...\n";
    hyp_out::t_spD3DMeshObject spD3DMesh;
    spD3DMesh.CreateInstance(hyp_out::CLSID_hypCObjectXFile,0);
    spD3DMesh->SetObject(m_spUnknownMesh);
    spD3DMesh->SaveD3DHypMesh(path);
}

The result is save in a Hyperion file. This file is an extension of the DirectX file format because new templates are defined.

template HypMatrix {
 <af8b31e1-36a0-11d5-a099-0080ad97951b>
 DWORD nRows;
 DWORD nColumns;
 array FLOAT Matrix[nRows][nColumns];
}

template HypNode {
 <5151b1c2-3f11-11d5-a099-0080ad97951b>
 DWORD Label;
 FLOAT X;
 FLOAT Y;
 FLOAT Z;
 DWORD Properties;
 DWORD DOF;
}

template HypBase {
 <5151b1c5-3f11-11d5-a099-0080ad97951b>
 DWORD Label;
 DWORD nRefNodes;
 array DWORD RefGlobalNodes[nRefNodes];
 array DWORD RefLocalNodes[nRefNodes];
}

template HypElement {
 <5151b1c6-3f11-11d5-a099-0080ad97951b>
 HypBase Base;
}

template HypSide {
 <5151b1c7-3f11-11d5-a099-0080ad97951b>
 HypBase Base;
}

template HypMesh {
 <5151b1c1-3f11-11d5-a099-0080ad97951b>
 DWORD nNodes;
 array HypNode nodes[nNodes];
 DWORD nSides;
 array HypSide sides[nSides];
 DWORD nElements;
 array HypElement elements[nElements];
}

It is sometimes handy to verify the validity of the computed matrix. That is why a force is applied on the nodes located on the top of the cube [line 7].

Parameter Description
px If bx is true, forces are applied on node in the plan which has x = pz for equation
py If by is true, forces are applied on node in the plan which has y = py for equation
pz If bz is true, forces are applied on node in the plan which has z = px for equation
bx Select the x plan
by Select the y plan
bz Select the z plan
fx Force applied on the selected node along the x-axis
fy Force applied on the selected node along the y-axis
fz Force applied on the selected node along the z-axis

void CDevMesh::SetForce(const t_real& px,const t_real& py,const t_real& pz,bool bx,
                        bool by,bool bz,const t_real& fx,const t_real& fy,const t_real& fz)
{
    m_spMeshMesh->SetForce(px,py,pz,bx,by,bz,fx,fy,fz);
}

The system is solved [line 8].

void CDevMesh::Solve()
{
    m_spMeshMesh->Render(); //displacements are found
    m_spMeshMesh->PostRender(); //displacement vector is added to the position vector
}

Two output formats can be generated. The first format is an ASCII file containing numerical data about the solid [line 9].

void CDevMesh::ShowMesh(const std::string& path)
{
    m_Stream<<"Show Mesh in "<<path<<"...\n";
    hyp_out::t_spShowMeshObject spShow;
    spShow.CreateInstance(hyp_out::CLSID_hypCObjectStdFile,0);

    spShow->SetOutput(path);
    spShow->SetObject(m_spUnknownMesh);
    spShow->ShowAll();

    //miscelleneous data
    spShow->ShowForceMask();
    spShow->ShowForces();
    spShow->ShowRenderMask();
    spShow->ShowDisplacements();
    spShow->CloseOutput();
}

The second format which follows the same scheme as the DirectX files saves the geometry of the solid uniquely [line 10]. So you can load the file into your favorite DirectX file viewer.

void CDevMesh::SaveMesh(const std::string& path)
{
    m_Stream<<"Save Mesh in "<<path<<"...\n";
    hyp_out::t_spD3DMeshObject spD3DMesh;
    spD3DMesh.CreateInstance(hyp_out::CLSID_hypCObjectXFile,0);

    spD3DMesh->SetObject(m_spUnknownMesh);
    spD3DMesh->SaveD3DHypMesh(path);
}

Command line

You could try the previous example by using HypDev with the following command line:

hpdev.exe -hypfile c:\cube.hyp -xfile c:\cube.x -txtfile c:\cube.txt /
   -g 2 2 2 4 4 4 -dof 0 0 0 0 0 1 1 1 1 -f  0 0 2 0 0 1 0 0 1000 –v

HypVisual

HypVisual displays the content of the Hyperion files. It also allows the user to apply forces on the solid and to generate temporal interpolations. Although a large amount of code is not directly connected to the Ephydryne components but to the MFC or to some DirectX objects, we will have a look at the implementation of the main functions.

Elastic vs. plastic deformations

Before going further, it is important to remember the hypothesis made in the first article, that is, those related to the study of elastic deformations uniquely. A deformation is elastic when a linear relation between the applied forces and the displacements exists. Moreover, during an elastic deformation, solids change in shape that returns when a stress is removed. If the deformation is not elastic, it is called a plastic deformation which is permanent. This sort of deformation is very difficult to handle because results depend not only on the initial state but also on intermediate states of the deformation.

Elastic deformations have been supposed in order to obtain real-time results. As an aside, spring systems, widely used in the video games, are based on the same hypothesis. However temporal interpolation will be used to simulate plastic or viscous-elastic deformations loosely. It is worth noting that it is not mechanically correct, but looks realistic enough.

Temporal interpolation

The temporal interpolation is based on two ideas:

  • Whereas elastic deformations are not permanent, our elastic deformations will be. Moreover, these deformations will be considered as key points of the temporal interpolation.
  • How the solid gets its deformed shape, that is, how the interpolation functions are defined, is up to the programmer.

HypVisual implements three interpolation schemes: linear, sinus and damped oscillations. Notice that whereas in spring systems node positions are almost computed for each displayed frame because of the time integration, the Hyperion method computes them only once and interpolates the entire scene.

Implementation

Like CDevMesh which is defined in the HypDev application, the MFC Document object contains four interfaces pointing to a same component:

class CHypVisualDoc {
 //. . .
 hyp_ker::IPtrUnknown m_spUnknownMesh;
 hyp_fem::t_spGeometricBase m_spBaseMesh;
 hyp_fem::t_spGeometricObject m_spObjectMesh;
 hyp_fem::t_spFEOMesh m_spMeshMesh;
//. . . 
};

When the application starts up, the CFEOMesh component is initialized through the Hyperion file.

BOOL CHypVisualDoc::OnOpenDocument(LPCTSTR lpszPathName)
{
 CWaitCursor wait;
 try {
  hyp_TRACE( ("Load Mesh from %s",lpszPathName) );
  hyp_out::t_spD3DMeshObject spD3DMesh;
  spD3DMesh.CreateInstance(hyp_out::CLSID_hypCObjectXFile,0);

  spD3DMesh->SetObject(m_spUnknownMesh);
  spD3DMesh->LoadD3DHypMesh(lpszPathName);

  m_spMeshMesh->InitMasks();
 } catch(hyp_ker::CComException hr) {
  hyp_NOTIFY( ("Error during the loading of the file") );
  return FALSE;
 }
 return TRUE;
}

To display the object, the DirectX MeshBuilder component, m_pMesh, is initialized by the following function.

void CHypMesh::Reset()
{
 m_pMesh->Empty(0);
 try {
  hyp_out::t_spD3DMeshObject spD3DMesh;
  spD3DMesh.CreateInstance(hyp_out::CLSID_hypCObjectXFile,0);
  spD3DMesh->SetObject(m_pHypMesh); //m_pHypMesh is a data member of the CHypMesh class
  spD3DMesh->InitializeD3DMeshBuilder(m_pMesh);
 } catch(hyp_ker::CComException hr) {
  hyp_FATAL( ("Error during the reset of the mesh") );
 }
 // . . .
}

The best way to understand how the application works is to try several simulations.

Does the method fulfill our objectives?

You are perhaps wondering whether results obtained by this method are correct or not. In the first article, obtaining real-time and realistic solutions was my objective.

Are the results realistic?

Of course, some tests have been carried out in order to check whether obtained solutions are accurate or not. I will now present one of the most relevant tests. In this test, the solid is a beam fixed at one of its extremities (z=0). The dimensions of the beam are 2 by 2 by 20 meters between the points (0,0,0) and (2,2,20). A force having for intensity (100,0,0) is applied on the node (0,1,20). 40 elements along the z-axis and 2 along the x and z axes make this beam up.

According to the Strength of Material, a theoretical solution is found.

s corresponds to the displacement of the beam's extremity along the x-axis. L and Igz are related to the geometry of the beam. The numerical solution corresponding to our problem is 2 meters. As you can see in the chart, solution found by Hyperion is very close from the theoretical solution. Solution found by a FEM software application called ANSYS has been added as a reference.

The Finite Element Method is one of the best engineering methods to resolve physical problems. It is proved by this case once again.

Are the results real-time?

Multiplication between the matrix K'-1r and the force vector is only the time-consuming part of the method because computation is almost done during the creation of the level. Whereas FEM is often slow, the adaptation implemented by the Ephydryne components is very fast and offers the same accuracy as the FEM. According to the video game requirements, the method could be considered real-time.





Next : Optimizations