Bojanovski

Members
  • Content count

    3
  • Joined

  • Last visited

Community Reputation

511 Good

About Bojanovski

  • Rank
    Newbie
  1. Capsule Inertia Tensor

    Although there are robust algorithms that calculate body mass, center of mass and inertia tensor based on input triangle mesh, there are several reasons why alternatives should be used when possible. Probably the first one is speed. When working with triangles we end up with O(n) algorithm, as we need to process every of n triangles. Calculating mathematically defined body such as capsule gets us O(1) algorithm. Secondly, often we want to create a rigid body for our physics simulation but have only one mesh, a very detailed one for rendering. In such cases it is inconvenient to construct a special mesh for physics calculations and would be much easier to pass a few arguments to a function for a specific geometric primitive. Last and not so significant (at least for games) is accuracy. It is reasonable to say that a mesh that consists of triangles will never truly have round parts of its surface. This goes for spheres, cylinders, capsules and many other primitives. So if we pass our capsule as a mesh we will end up with slightly incorrect results. The analytical method that will be presented here provides accurate results. It is assumed that the reader has insight in theory behind inertia tensors and/or has an existing physics system that can make use of such a matrix. Knowledge in multivariate calculus is also assumed. Concept Firstly, what is meant by saying capsule? Well, simply put, it is a cylinder that (instead of flat ends) has hemispherical ends. By cylinder I mean a circular one (not elliptical). Hemispheres have the same radius. It should also be mentioned that the given body is solid (not hollow). Figure 1. Capsule definition. Where H is height of the cylinder part and R is radius of the hemisphere caps. This is the coordinate system that has its origin in the center of the mass of the capsule and whose axes are the axes which we will be calculating moments of inertia for. Figure 2. Capsule decomposition. The approach that we will be using to calculate the inertia tensor can be seen from Figure 2. The body will be decomposed into three parts: upper hemisphere, lower hemisphere and cylinder. Inertia tensors will be calculated for each of them and then just summed together to result in a complete capsule tensor. Here are given, in Cartesian coordinates, the well-known equations for moments and products of inertia needed for the inertia tensor in general. (eq. 1) V represents the three dimensional region of integration and dm is an infinitesimal amount of mass at some point in our capsule. The integrand is simply squared distance from the axis. (eq. 2) Note that in eq. 2 products of inertia are equal to zero. There exists a theorem that says that it is possible to find three (mutually perpendicular) axes for every body so the tensor produced from those axes has zero products of inertia. Those axes are called the principal axes. Furthermore, for bodies with constant density an axis of rotational symmetry is a principal axis. We have three perpendicular axes of rotational symmetry for our capsule. First one is the y axis of continuous rotational symmetry and then there are x and z axes of discrete rotational symmetry. I will not go into detail about what axes of rotational symmetry are, but I recommend to go and check it out. (eq. 3) Since we will integrate over space eq. 3 will be used. If density is required to be some other constant than 1, the end result can simply be multiplied by that constant. Cylinder Before we dive into integration here is the Cartesian coordiante system we will be using for cylinder: Figure 3. Cylinder and its position relative to coordinate system. Let's start with easiest to compute moment of inertia, the one around the y axis. As previously mentioned, integrand is just a squared distance from the axis. With that in mind we can leave the Cartesian coordinate system and use the cylindrical one. The y axis remains unchanged. Also note that solutions will be written immediately without showing any steps. (eq. 4) First we add up (integrate) over 2*pi*r interval to get the moment of inertia of a circular curve around the y axis. After that we integrate that curve over the interval R to get the moment of inertia of a disc surface perpendicular to the y axis. Lastly those discs are added up across [-H/2, H/2] interval to get the moment of inertia of a whole cylinder. The integral for the mass of a cylinder is very similar and follows the same intuition. It is given by: (eq. 5) Now, slightly more complicated integrals are the ones for moments of inertia around x and z axis. Those are equal, so only one calculation is needed. Note that we are back in Cartesian coordinates for this one and the integral is set up like we are calculating Ixx. (eq. 6) This is it for the cylinder as I will not go into detail about intuition for this integral since there is more work to be done for hemisphere caps. Hemisphere caps The following is how the hemisphere is defined relative to Cartesian coordinate system for the purpose of integration: Figure 4. Hemisphere and its position relative to coordinate system. The easiest to calculate moment of inertia of hemispheres is also the one around y axis. (eq. 7) We are in the cylindrical coordinate system and the intuition is similar to eq. 4. The only difference is that now the radius of a disc we need to integrate is a variable of the y position of a disc (sqrt(R^2 - y^2)). Then we just integrate those discs from 0 to R and we end up with the whole hemisphere region. As for the cylinder, the integral for the mass of a hemisphere follows the same intuition and is given by: (eq. 8) Now, when we try to calculate the moments of inertia around x and z axis (which are equal), things get tricky. Note that integral is set up like we are calculating Ixx: (eq. 9) Figure 5. Center of mass of a hemisphere. As it can be seen in figure 5, center of mass is not in the origin of the coordinate system, but the axis for which we calculated the moment of inertia is. In order to work with this moment of inertia (to apply Steiner's rule) we need it to be in the center of mass. This is where we calculate the distance b and use it in reverse Steiner's rule: (eq. 10) (eq. 11) Where Icm is moment of inertia of an axis that goes through the center of mass and m is hemisphere mass from eq. 8. Now it's finally possible to calculate Ixx and Izz for our hemisphere caps. We can now apply Steiner's rule to translate the axes from the center of mass of a hemisphere to the center of mass of the whole body (capsule): (eq. 12) Moments of inertia for the hemisphere cap on the bottom of the capsule do not differ to those here. The tensor (eq. 13) Equations in eq. 13 give us separated masses of cylinder and hemisphere as well as the mass of the whole body. Notice how mass of the hemisphere (mhs) is multiplied by two. This is, of course, because there are two hemispheres on both ends of the capsule. Also, note our previous assumption in which density is equal to one unit of measurement, which is why the mass is equal to volume. If needed mcy and mhs can simply be multiplied by some constant density and the results will be accurate. The given code is written in such way. The full tensor uses this values and is given by: (eq. 14) Although previously shown formulas for moments of inertia are not given by mcy and mhs, by substituting those values equality can be easily shown. The parts that represent moments of inertia of a hemisphere are multiplied by two, because we have two of them. Code The following code implementation is given in C-like language and is fairly optimized. #define PI 3.141592654f #define PI_TIMES2 6.283185307f const float oneDiv3 = (float)(1.0 / 3.0); const float oneDiv8 = (float)(1.0 / 8.0); const float oneDiv12 = (float)(1.0 / 12.0); void ComputeRigidBodyProperties_Capsule(float capsuleHeight, float capsuleRadius, float density, float &mass, float3 ¢erOfMass, float3x3 &inertia) { float cM; // cylinder mass float hsM; // mass of hemispheres float rSq = capsuleRadius*capsuleRadius; cM = PI*capsuleHeight*rSq*density; hsM = PI_TIMES2*oneDiv3*rSq*capsuleRadius*density; // from cylinder inertia._22 = rSq*cM*0.5f; inertia._11 = inertia._33 = inertia._22*0.5f + cM*capsuleHeight*capsuleHeight*oneDiv12; // from hemispheres float temp0 = hsM*2.0f*rSq / 5.0f; inertia._22 += temp0 * 2.0f; float temp1 = capsuleHeight*0.5f; float temp2 = temp0 + hsM*(temp1*temp1 + 3.0f*oneDiv8*capsuleHeight*capsuleRadius); inertia._11 += temp2 * 2.0f; inertia._33 += temp2 * 2.0f; inertia._12 = inertia._13 = inertia._21 = inertia._23 = inertia._31 = inertia._32 = 0.0f; mass = cM + hsM * 2.0f; centerOfMass = {0.0f, 0.0f, 0.0f}; } It would seem that centerOfMass is useless, but I have left it here because it is important part of rigid body properties and often a requirement for physics engines. Conclusion Capsules defined in a way which was presented here are very commonly used in games and physical simulations, so this tensor should be of use to anyone building their own 3D game engine or similar software. Although, right-handed Cartesian coordinate system was used in this article, you can also use the code in left-handed system as long as y axis is the longitudinal axis (the axis that goes through caps). The somewhat tedious processes of integration were skipped and only the end results were shown. This is mostly because it would take too much space. If you are curious whether those expressions are correct, you can try them on Wolfram or try to integrate them yourself. Also, you can follow me on Twitter. Article Update Log December 1, 2014: Initial release December 3, 2014: Updated figures, equations and text
  2. Capsule Inertia Tensor

    Whoa, that's a lot of work you gave me, but your notes are sound and I did my best to update the article. If there is anything else, let me know.   Thanks, Bojan
  3. Capsule Inertia Tensor

    Thanks for pointing cm (center of mass) out. The new version of the article has that part a lot clearer now. As for your question about density, the answer is yes, it is as simple as multiplying the masses. There is nothing more to it as long as it is constant. The new version of the article has that part also explained better.   Thank you, Bojan
  4. To achieve high visual fidelity in cloth simulation often requires the use of large amounts of springs and particles which can have devastating effects on performance in real time. Luckily there exists a workaround using B-splines and hardware tessellation. I have, in my approach, used a grid of only 10x10 control points to produce believable and fast results. CPU is tasked only with collision detection and integration of control points which is computed fast considering that there are only 100 of those and that it can easily run on a separate thread. All of B-spline computation is done on GPU or, to be more specific, in the domain shader of the tessellation pipeline. Since GPU code is the only part of this implementation involving B-spline computation, all code that follows is written in HLSL. B-Splines I will not go into details about B-splines but some basics should be mentioned. So here is the spline definition (note that there are actually n+1 control points, not n) (eq. 1) N - basis functions B - control points d - degree u - input parameter The degree of the curve d is a natural number that must be so that 1 Figure 1. B-spline curve The extension from curves to surfaces is simple and is given by (eq. 2) Basis function values for each, u and v parameter, are computed separately and usually stored in some array before they are used in this formula. These function values are used to determine how much every control point is influencing the end result for certain input parameter u (or u and v for surfaces). The definition for basis functions are where things get tricky. (eq. 3) This recursion ends when d reaches zero: Where is a knot in a knot vector - a nondecreasing sequence of scalars. Open (nonperiodic) and uniformly spaced knot vector is used here. Also for every i. As stated before, n + 1 is the actual number of control points (according to definition), but this is inconvenient for our code. This is why, in code, the denominator is subtracted by 1. Here is the definition and code implementation: float GetKnot(int i, int n) { // Calcuate a knot form an open uniform knot vector return saturate((float)(i - D) / (float)(n - D)); } This recursive dependencies can be put into table and it can easily be seen that for a given u only one basis function N in the bottom row is not zero. Figure 2. Recursive dependencies of a basis functions (n=4, d=2). For a certain u the only non zero values are in the rectangles. This is the motivation behind De Boor's algorithm which optimizes the one based on mathematical definition. Further optimization is also possible like the one from the book by David H. Eberly. I have modified David's algorithm slightly so that it can run on the GPU and added some code for normal and tangent computation. So how do we get the right i so that for given u? Well considering that knot vector is uniformly spaced it can be easily calculated. One thing to note though, since u when u=1 we will end up with incorrect values. This can be fixed by making sure a vertex with a texture coordinate (either u or v) equal to 1 is never processed, which is inconvenient. The simpler way is used here, as we simply multiply the u parameter by a number that is "almost" 1. int GetKey(float u, int n) { return D + (int)floor((n - D) * u*0.9999f); } The last thing we need before any of this code will work is our constant buffer and pre-processor definitions. Although control points array is allocated to its maximum size, smaller sizes are possible by passing values to gNU and gNV. Variable gCenter will be discussed later, but besides that all variables should be familiar by now. #define MAX_N 10 // maximum number of control points in either direction (U or V) #define D 2 // degree of the curve #define EPSILON 0.00002f // used for normal and tangent calculation cbuffer cbPerObject { // B-Spline int gNU; // gNU actual number of control points in U direction int gNV; // gNV actual number of control points in V direction float4 gCP[MAX_N * MAX_N]; // control points float3 gCenter; // arithmetic mean of control points // ... other variables }; The function tasked with computing B-spline inputs just texture coordinates (u and v) and uses it to compute position, normal and tangent. We will add the Coordinates u and v a small epsilon value to produce an offset in coordinate space. These new values are named u_pdu and v_pdv in code and here is how they are used to produce tangent and normal: (eq. 4) Now, as mentioned earlier, basis function values are computed and stored in separate arrays for u and v parameter, but since we have additional two parameters u_pdu and v_pdv a total of four basis functions (arrays) will be needed. These are named basisU, basisV, basisU_pdu, basisV_pdv in code. GetKey() function is also used here to calculate the i so that for given u as stated before and separately one i for given v. One might think that we also need separate i for u_pdu and v_pdv. That would be correct according to definition, but the inaccuracy we get from u_pdu and v_pdv potentially not having the correct i and thus having inacurate basis function values array is too small to take into account. void ComputePosNormalTangent(in float2 texCoord, out float3 pos, out float3 normal, out float3 tan) { float u = texCoord.x; float v = texCoord.y; float u_pdu = texCoord.x + EPSILON; float v_pdv = texCoord.y + EPSILON; int iU = GetKey(u, gNU); int iV = GetKey(v, gNV); // create and set basis float basisU[D + 1][MAX_N + D]; float basisV[D + 1][MAX_N + D]; float basisU_pdu[D + 1][MAX_N + D]; float basisV_pdv[D + 1][MAX_N + D]; basisU[0][iU] = basisV[0][iV] = basisU_pdu[0][iU] = basisV_pdv[0][iV] = 1.0f; // ... the rest of the function code Now for the actual basis function computation. If you look at figure 2. you can see that non zero values form a triangle. Values of the left diagonal and right vertical edge are computed first since each value depends only on one previous value. The interior values are then computed using eq. 3. Every remaining value of the basis functions array is simply left untouched. Their value is zero but even if it would be some unwanted value it doesn't matter as will be seen later. // ... the rest of the function code // evaluate triangle edges [unroll] for (int j = 1; j Also, you can follow me on Twitter and check out this youtube video which demonstrates explained methods in action. Hope you like it! Article Update Log September 11, 2014: Initial release
  5. DX11 warning C4005

    I skimmed through directxtk a little but I could not find functions for loading .fxo file. It only says it offers built-in shaders to create functionality equivalent of BasicEffect from XNA. Also, I am hearing that directx 11.1 handles effects differently. What are the future plans from microsoft, will directx 11.2 in win 8.1 have this things fixed?     EDIT:   This tutorial from Frank D. Luna shows how to use hlsl (compile, load, send parameters such as constant buffers, SRVs, etc.) without using deprecated Effects11 library.   He also said: "In Metro applications, you cannot link with D3DCompiler.lib. Metro only allows certain APIs to be used for security (this is also why D3DX library and Effects cannot be used).", what answers one of my previous questions.   So I decided to keep using effects11.lib. As for the warning, I created this header which I call when I need directx headers: #ifndef DIRECTX11HEADERS_H #define DIRECTX11HEADERS_H #pragma warning( disable : 4005 ) #include <d3d11.h> #include <d3dx11.h> #include <d3dx11effect.h> #pragma warning( default : 4005 ) #endif
  6. DX11 warning C4005

    Hi!   So I've been trying to do this for far too long, but simply every option leads me to a dead end. I want to use DirectX 11 in visual studio 2012 without getting that damn warning C4005. My project is dependant on d3dx11 library so it has to be dx11, not dx11.1, unless I find some solution to manage my textures and effects loading without d3dx11!   I know what happened to windows 8 sdk and how it now includes directx 11.1 (except d3dx library) and when  I include my june 2010 version it all gets mixed up so bunch of redefinitions pops up.   So what is the easiest way to prevent visual studio from looking for directx headers in windows 8 sdk?   Also, can somebody, that has better understanding in microsoft's way of doing things, explain to me why did they create directx sdk without built-in libraries and functions for an important task such as textures and effects loading?? :S :'(
  7. So, if anyone has some recommendations, that would be great.   This is the best I found so far: 'Game Physics' by David H. Eberly.