Advise algorithm

[Jinto]

Advise algorithm. How rapidly determine whether a point is inside or outside of the mesh.

[CuteAlien]

I don't think there is an easy and fast solution for this. Without reading up, my first guess would be that you try to split your mesh into convex sub-meshes. Then you can check if a point is on the same side of all triangles for each of the sub-meshes. But probably there's optimized algorithms out there for that stuff.

So easiest solution - find a lib that supports that. Physics libraries often come with collision libraries, so you can check if one of those supports that.

But if it's for realtime re-consider even trying to find that out. In realtime you work usually instead with simple collision-meshes (boxes, spheres, ellipsoids).

[Mel]

convex decomposition plus convex detection is the simplest approach to perform an inside/outside test

[chronologicaldot]

Your mesh needs to be divided up into sub-regions, even if not sub-meshes. Personally, I would divide my mesh into smaller and smaller regions (up to a point of good optimization at least) - possibly with layers of division, if that makes sense - until I could reduce the collision algorithm to something simple like "is it within the radius" - a whole lot faster than checking "is it passed the triangle).

I've already started on something like this and created basic implementations, but mostly all I have are abstract classes. It'd take awhile for me to code up an example of their usage with irrlicht meshes.

Edit: And I have no idea what convex decomposition is, so I'm looking it up.

Edit 2: I forgot to mention something very important to my implementation: I use "centers", which are basically the centers of the simple regions (like spheres), and I determine which of these "centers" the point of interest is nearest to. Then I can do a simple radius comparison (or something like that, depending on the shape of the simple region).

[Abraxas)]

If your mesh is roughly prism shaped, you can use the boundingbox

[Jinto]

Ok Thanks all

[Klunk]

some code from the 3dsMax SDK.... it uses there internal structure but should be pretty easy to port

Code: Select all

 
BOOL IsBadFace(Mesh* mesh, int index)
{
    DbgAssert(mesh);
    DbgAssert(index >= 0); DbgAssert(index < mesh->numFaces);
    return ((mesh->faces[index].flags & FACE_WORK) ? TRUE : FALSE);
}
 
bool IsFaceAboveOrigin(Point3 v1, Point3 v2, Point3 v3)
// defines if interior of the given face is above Point3::Origin
{
    Point3 a = v2 - v1;
    Point3 b = v3 - v1;
    double det0 = double(a.x)*b.y - double(a.y)*b.x;
    double det1 = double(v1.y)*b.x - double(v1.x)*b.y;
    if (det1 == 0.0) return false;
    double x = det1/det0;
    if (x <= 0.0) return false;
    double det2 = double(a.y)*v1.x - double(a.x)*v1.y;
    if (det2 == 0.0) return false;
    double y = det2/det0;
    if (y <= 0.0) return false;
    if (x+y >= 1.0) return false;
    double z = v1.z + x*a.z + y*b.z;
    return ( z > 0.0);
}
 
bool IsPointInsideMesh(Mesh* mesh, Point3 p)
// the method finds number of faces that are above the given point
// if the number is odd then the point is considered "inside" the mesh
// therefore the mesh doesn't have to have closed surface
{
    int numAbove = 0;
    for(int i=0; i<mesh->getNumFaces(); i++) {
        if (IsBadFace(mesh, i)) continue;
        if (IsFaceAboveOrigin(  mesh->verts[mesh->faces[i].v[0]] - p,
                                mesh->verts[mesh->faces[i].v[1]] - p,
                                mesh->verts[mesh->faces[i].v[2]] - p) )
            numAbove++;
    }
 
    return ((numAbove % 2) == 1);
}
 

it assumes the mesh is continuous with no holes

the conversion to Irrlicht may look something like this (please note this is untested, i did a quick bit of code as i thought you maybe unfamiliar with the internal structures of max)

Code: Select all

bool IsFaceAboveOrigin(vector3df v1, vector3df v2, vector3df v3)
{
    vector3df a = v2 - v1;
    vector3df b = v3 - v1;
    double det0 = double(a.X)*b.Y - double(a.Y)*b.X;
    double det1 = double(v1.Y)*b.X - double(v1.X)*b.Y;
    if (det1 == 0.0) return false;
    double x = det1/det0;
    if (x <= 0.0) return false;
    double det2 = double(a.Y)*v1.X - double(a.x)*v1.Y;
    if (det2 == 0.0) return false;
    double y = det2/det0;
    if (y <= 0.0) return false;
    if (x+y >= 1.0) return false;
    double z = v1.Z + x*a.Z + y*b.Z;
    return ( z > 0.0);
}
     
bool IsPointInsideMeshBuffer(SMeshBuffer* meshbuffer, vector3df& p)
{
    int numAbove = 0;
    int numindices = meshbuffer->getIndexCount();
    u16* indices = meshbuffer->getIndices();
    S3DVertex* verts = (S3DVertex*)meshbuffer->getVertices();
 
    for(int i=0; i < numindices; i+=3) 
    {
        if (IsFaceAboveOrigin(  verts[indices[i]].pos - p,
                                verts[indices[i+1]].pos  - p,
                                verts[indices[i+2]].pos  - p) )
            numAbove++;
    }
 
    return ((numAbove % 2) == 1);
}

[Jinto]

it's work fine but some points shows as inside.

Code: Select all

 
IMeshBuffer* meshBuffer=o_mesh->getMeshBuffer(0);
printf("%i \n",o_mesh->getMeshBufferCount());
printf("%f  %f  %f \n", meshbox.MinEdge.X,meshbox.MinEdge.Y,meshbox.MinEdge.Z);
printf("%f  %f  %f \n", meshbox.MaxEdge.X,meshbox.MaxEdge.Y,meshbox.MaxEdge.Z);
 
f32 delta_x=(meshbox.MaxEdge.X-meshbox.MinEdge.X)/size_x;
f32 delta_y=(meshbox.MaxEdge.Y-meshbox.MinEdge.Y)/size_y;
f32 delta_z=(meshbox.MaxEdge.Z-meshbox.MinEdge.Z)/size_z;
 
for(int xx = 0; xx <= size_x; xx = xx + 1)
      for(int yy = 0; yy <= size_y; yy = yy + 1)
          for(int zz = 0; zz <=size_z; zz = zz + 1){
              int index=xx+yy*(size_x+1)+zz*(size_x+1)*(size_y+1);
 
              
 
            core::vector3df testpoint=core::vector3df(meshbox.MinEdge.X+xx*delta_x,meshbox.MinEdge.Y+yy*delta_y,meshbox.MinEdge.Z+zz*delta_z);
 
            
            if(IsPointInsideMeshBuffer(meshBuffer, testpoint)) {
              ISceneNode* kr=smgr->addCubeSceneNode(0.02f);
              kr->setPosition(testpoint);}
              }

[Klunk]

guess you'll have to look at those with the debugger and see what's what

[Abraxas)]

Advise algorithm. How rapidly determine whether a point is inside or outside of the mesh.

You wanted rapid so that always comes at the expense of accuracy. If your object is spherical, you can use boundingbox to determine it's radius at load time, and then do a distance calculation instead.

[Jinto]

I'm trying to make a quick algorithm, using technology based on Marching Cubes to obtain the low-poly LOD mesh . To do this, for any meshes need to get the points cloud inside the initial mesh.

[Klunk]

I've run that code I posted (the max variation) and I cannot get the code to error and on some pretty varied and whacky meshes. It seems from here it does a pretty good job though not particularly swiftly.

[Jinto]

[Klunk]

it would be more helpful if you posted the original mesh.

[Jinto]

Let's try meshes from http://irrlicht.sourceforge.net/forum/v ... od#p267311