# grouping polygons in a 3ds model for boxes collision detection.

## Recommended Posts

Hello, I want to use 3D collision detection. I've read some, and I figured that most 'good' techniques is a bit over my head for me, so I thought the easiest way to do collision detection which is atleast a little good is using boxes. In example, when I have a model of a human, every lim, the head and the torso is in a box. I first came with the idea to make a seperated file that contains all the information of each frame, but it isn't the best way to do it, because you don't have a clue where to place the boxes. So I gues the easiest way to group polygons, and then generate a box from the information of the polygons. So to come to my question, is it possible to group polygons in a .3ds model? If so, how do I know which polygons belong to which group? I'm using lib3ds to read out the information of my 3ds model. And if it's not possible, are there some other good alternatives? Thanx Hylke

##### Share on other sites
I've successfully used a box-per-bone collision for bullet V characters before. You can either compute the boxes from the source mesh (which is a little tricky, but essentially if a vert is skinned to a bone, just add the vertex to that bones bbox using the bind pose position of the vertex), but for more control I would just have the artists create another version of the character with a box attached to each bone. That way, what you see in max will be your collision model and it's easy to tune.

You could also use spheres (multiple per bone) in a similar way.

-Steve.

##### Share on other sites
I've successfully used a box-per-bone collision for bullet V characters before. You can either compute the boxes from the source mesh (which is a little tricky, but essentially if a vert is skinned to a bone, just add the vertex to that bones bbox using the bind pose position of the vertex), but for more control I would just have the artists create another version of the character with a box attached to each bone. That way, what you see in max will be your collision model and it's easy to tune.

You could also use spheres (multiple per bone) in a similar way.

-Steve.

##### Share on other sites
Quote:
 Original post by sbroumleyI've successfully used a box-per-bone collision for bullet V characters before.

Great to hear, because I also want to use weapons in my game.
Quote:
 You can either compute the boxes from the source mesh (which is a little tricky, but essentially if a vert is skinned to a bone, just add the vertex to that bones bbox using the bind pose position of the vertex), but for more control I would just have the artists create another version of the character with a box attached to each bone. That way, what you see in max will be your collision model and it's easy to tune.

I gues I'Il pick the first idea.
But the way you told it how to do it, looks a little complicated, could you give a little code example to clear things up a bit?
Hylke

##### Share on other sites
You could try something like this code (BTW - I haven't tested this - it's just for demonstration purposes).

Once you have your bind pose space bounding boxes as computed below, for collision detection with fast bullets, you can transform each of the box corner vertices (8 of them per box) into world space using your computed skeleton animation matrices (the same ones you use for rendering the skinned mesh with) and then perform a ray cast versus oriented bounding box or whatever you need to do.

Hope that helps,
Steve.

PS - To make sure your computations and data are correct, always implement a debug render function so you can see where your boxes are.

//==============================================================================// Simpler vector classclass vector3{public:    // Data    float m_X,          m_Y,          m_Z;    // Functions, operators etc...};//==============================================================================// Simple axis aligned bounding box classclass bbox{public:    // Data    vector3 m_Min,      // Minimum bound            m_Max;      // Maximum bound    // Functions    void Clear( void )    {        // Set min to biggest number, sets max to smallest number        m_Min.Set( FLT_MAX, FLT_MAX, FLT_MAX );        m_Max.Set( -FLT_MAX, -FLT_MAX, -FLT_MAX );    }    // Adds vector3 to bounds (could be done as an operator)    void Add( const vector3& V )    {        // Update min        m_Min.m_X = min( m_Min.X, V.m_X );        m_Min.m_Y = min( m_Min.Y, V.m_Y );        m_Min.m_Z = min( m_Min.Z, V.m_Z );                // Update max        m_Max.m_X = max( m_Max.X, V.m_X );        m_Max.m_Y = max( m_Max.Y, V.m_Y );        m_Max.m_Z = max( m_Max.Z, V.m_Z );    }};//==============================================================================// Simple vertex class to demonstrate computing bboxes#define MAX_VERTEX_WEIGHTS = 4      // Engine specificclass vertex{public:    vector3 m_Position;                             // Bind pose position    int     m_nSkinWeights;                         // Number of weights in vertex    float   m_SkinWeights[ MAX_VERTEX_WEIGHTS ];    // Weights values    int     m_iSkinBone  [ MAX_VERTEX_WEIGHTS ];    // Bone indices};//==============================================================================// Simple skeleton mesh class class skeleton{public:    // Data    int     m_nVertices;        // # of vertices    vertex* m_Vertices;         // Array of vertices    int     m_nBones;           // # of bones    bbox*   m_BoneBBoxes;       // Array of bones    // Functions    void    ComputeBoneBBoxes( void );    // etc...};//==============================================================================// Compute bone bounding boxes from vertices// (assumes vertex and bone members are allocated/initialized)void skeleton::ComputeBoneBBoxes( void ){    int  i, j;    // Clear bone bounding boxes    for( i = 0; i < m_nBones; i++ )    {        m_BoneBBoxes[i].Clear();    }    // Loop through vertices and accumulate into bone bounding boxes    for( i = 0; i < m_nVertices; i++ )    {        // Lookup vertex        const vertex& Vertex = m_Vertices[i];        // Loop through vertex skin info        for( j = 0; j < Vertex.m_nSkinWeights; j++ )        {            // Lookup bone index            s32 iBone = Vertex.m_iSkinBone[ j ];            ASSERT( iBone >= 0 );            ASSERT( iBone < m_nBones );            // Add to bone bounding box?            // TO DO: Tweak threshold for different fits            if( Vertex.m_SkinWeights[ j ] > 0.1f )              {                // Include vertex position in bone bounding box                m_Bones[ iBone ].Add( Vertex.m_Position );            }        }    }}//==============================================================================

##### Share on other sites
I'Il take a closer look at the code when I have some more time.
But what I understand of it, it creates a box around the bones.
But what if I don't have any bones(I also want to use lib3ds to create my level width)?
Hylke

##### Share on other sites
Collision with a static world is a whole different can of worms. There are lots of algorithms/methods on how you can represent your static world and implement broad-phase collision. Search the net for ideas.

If you're interested in "baking your own" static world collision, a very simple approach is to simply break your max level up into pieces (so that each piece is an object in max). This can be done at the art/design level very easily and allows you to build a level out of modular pieces. For each level object compute the bounding box (similar to the previous code, but it's faster since there's no skinning).

Once you have your level broken up into objects, your broad phase check can simply check the overlap of your movment primitives bounding box against each level-objects bounding box; if they overlap, then proceed to check each triangle (narrow phase). Depending upon what your memory requirements are, for the narrow phase you could compute each triangles bounding box on the fly, or pre-compute a bounding box per triangle. If the triangles bounding-box overlaps with your moving primitive/ray, the proceed to your final triangle versus primitive check. NOTE: A simple optimization is to have a low-poly collision model for each level-object. This is the technique I've used successfully on a few commercial games (Turok series, TribesPS2, Area51).

##### Share on other sites
Quote:

About that, breaking up the level in to objects, would that mean I would need to make a .3ds file for each object in my world?

And i've also got a question about the little source you posted.
What kind of information does the variable m_SkinWeights contain?Is it like, "my weight is ... pounds"?
Thank you for your replies so far.
Hylke

##### Share on other sites
lol. I'd assume it's the bone weight for the smooth skinning algorithm. ;)

##### Share on other sites
Quote:
 Original post by timwlol. I'd assume it's the bone weight for the smooth skinning algorithm. ;)

I'm not really a 3DSMAX expert, nor am I a lib3ds expert, so what would you need that for?

##### Share on other sites
Ok, I've read some aobut Skin Weights.
But I still don't understand the following part of the code:
        for( j = 0; j < Vertex.m_nSkinWeights; j++ )        {            // Lookup bone index            s32 iBone = Vertex.m_iSkinBone[ j ];            ASSERT( iBone >= 0 );            ASSERT( iBone < m_nBones );            // Add to bone bounding box?            // TO DO: Tweak threshold for different fits            if( Vertex.m_SkinWeights[ j ] > 0.1f )              {                // Include vertex position in bone bounding box                m_Bones[ iBone ].Add( Vertex.m_Position );            }        }

I found on the inet that the formula for calculating vertices from vertices with multiple Skin Weights looks like this:
Quote:
 vBlend = V1W1 + … + Vn-1Wn-1 + Vn (1.0-Wi)

What I don't understand about is, this is the formula to calculate one vertex, but you need multiple vertices for it.What are these vertices, the place of the center of each bone?
And if that is true, wouldn't the code(the code I did not understand) look like this:
vertex finalvertex;for(j = 0;j < Vertex.m_nSkinWeights;j++){    finalvertex.m_X += BoneCenters[ Vertex.m_iSkinBone[j] ].m_X * Vertex.m_SkinWeights[j];    finalvertex.m_Y += BoneCenters[ Vertex.m_iSkinBone[j] ].m_Y * Vertex.m_SkinWeights[j];    finalvertex.m_Z += BoneCenters[ Vertex.m_iSkinBone[j] ].m_Z * Vertex.m_SkinWeights[j];}for(j = 0;j < Vertex.m_nSkinWeights;j++)    m_Bones[ Vertex.m_iSkinBone[j] ].Add(finalvertex);

##### Share on other sites
The code assumes the vertices are already in the bind pose position (which they should be if you are using a skinning algorithm). For example this is the T-Pose (arms and legs straight out) of your character in max.

The pipeline for computing vertices during an animation is almost correct in your code, but you wouldn't use the bone centers, you would use the bones local to world transform (a matrix). If you did the same thing with the bone matrices being the T-Pose transform, the vertices would end up being in the T-Pose position (unaltered) so I just skipped that part.

Skinning is a whole other topic. If you need more info/help, just let me know.

##### Share on other sites
Why do you use:
            if( Vertex.m_SkinWeights[ j ] > 0.1f )              {..            }

Is that to make sure that those boxes don't get to large(because I can imagine, the lower the weight, the further the bone is away)?
Hylke

##### Share on other sites
Yes - you are correct. Tweaking that number will change the size of the bounding box depending on the skinning fall off of your vertices. The closer to one it is, then the smaller the bouding box will be and vice versa.

##### Share on other sites
Ok, thanx.
I think i'm hooked for some time now :-p

## Create an account

Register a new account

• ## Partner Spotlight

• ### Forum Statistics

• Total Topics
627689
• Total Posts
2978648

• 13
• 14
• 12
• 10
• 12