Sign in to follow this  
hylke2

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 this post


Link to post
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.

Let me know if you need any more info.
-Steve.

Share this post


Link to post
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.

Let me know if you need any more info.
-Steve.

Share this post


Link to post
Share on other sites
Quote:
Original post by sbroumley
I'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?
Thanx in advance,
Hylke

Share this post


Link to post
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 class
class vector3
{
public:
// Data
float m_X,
m_Y,
m_Z;

// Functions, operators etc...
};

//==============================================================================

// Simple axis aligned bounding box class
class 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 specific
class 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 this post


Link to post
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)?
Thanx in advance,
Hylke

Share this post


Link to post
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 this post


Link to post
Share on other sites
Quote:
Original post by sbroumley
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).

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 this post


Link to post
Share on other sites
Quote:
Original post by timw
lol. 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 this post


Link to post
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 this post


Link to post
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 this post


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

In your code?
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)?
Thanx in advance,
Hylke

Share this post


Link to post
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 this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this