Jump to content
  • Advertisement
Sign in to follow this  
jpetrie

MD2 Triangle Adjacency

This topic is 4833 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I need to compute a triangle adjacency table (e.g., for a given triangle at index n with a mesh, what are the three triangle indices that share the edges of triangle n). My algorithm is detailed below. The problem I am running into is that some models (in the MD2 format), but not all, seem to have triangles with unshared edges. These edges don't cause noticable seems when the object is rendered, but they are a minor annoyance. I was wondering if anybody who has worked with the MD2 format (this is my first time using it -- and using a different format isn't really an option) could tell me if this is typical? I know that the format doesn't need to make any guarantees that the model is closed, and that these seems could be the product of poor modelling or a poor exporter; I don't really want to put the blame there, though, unless I have good reason to. I am getting my test models from the Polycount website. The relevant code looks like this:
struct AdjacencyInfo
{
  int  neighbor[3];
};

typedef std::vector< AdjacencyInfo >  AdjacencyTable; 

AdjacencyTable BuildAdjacencyTable(const MD2Model &source)
{
  // -1 means "no triangle shares this edge"
AdjacencyInfo   empty = { {-1,-1,-1} };
AdjacencyTable  table;

  // Resize and fill the table with dummy adjacency information.
  table.resize(source.GetTriangleCount());
  std::fill(table.begin(),table.end(),empty);
  
  // For each triangle...
  for(int i = 0; i < source.GetTriangleCount(); ++i)
  {
  MD2Model::Triangle  t = source.GetTriangle(i);
  
    // For each edge...
    for(int j = 0; j < 3; ++j)
    { 
      // The edge on t is from p0 to p1. On the adjacent
      // triangle (if any), that edge will be p1 to p0.
      // Find and store that triangle index.
    unsigned short  p0 = t.vtxIdx[j];
    unsigned short  p1 = t.vtxIdx[(j + 1) % 3];
    
      int res = FindEdge(p1,p0,source);
      table.neighbor[j] = res;
    }
  }
}

int FindEdge(unsigned short p0,unsigned short p1,const MD2Model &source)
{
  for(int i = 0; i < source.GetTriangleCount(); ++i)
  {
  MD2Model::Triangle  t = source.GetTriangle(i);
  
    for(int j = 0; j < 3; ++j)
    {
    unsigned short  v0 = t.vtxIdx[j];
    unsigned short  v1 = t.vtxIdx[(j + 1) % 3];
    
      if(v0 == p0 && v1 == p1)
        return (i);
    }
  }
  
  // Not found.
  return (-1);
}


If anybody sees anything wrong with that that I am missing (or if you know of a better way) please let me know!

Share this post


Link to post
Share on other sites
Advertisement
Quote:
The problem I am running into is that some models (in the MD2 format), but not all, seem to have triangles with unshared edges.
At first glance, your code looks right to me. I don't know that much about modelling, but I've heard that gaps, t-junctions, and other degeneracies are fairly common (perhaps more so with some modelling packages than others).

There may be some visual debugging you could do. For example, render unshared edges in red to see where they are and whether the gap is visible. There are also things you can do (such as welding) to repair a mesh if needed.

Again though my experience with modelling is minimal so I may be way off about this.

Share this post


Link to post
Share on other sites
one thing that may put a hamper into your code: a fixed vertex in space may have several different texture co-ordinates, so the vertex gets duplicated... now the MD2 format itself does not do this (since the "glcommands" part of the md2 file gives for each triangle strip/triangle fan a texture co-ordinate and a vertex index) but if you duplicating the vertexes tht have multiple texture co-ordinates (so you can use vertex arrays/VBOs) then you have to calculate your edges BEFORE you do this translation.... it also may be a good idea to check if the vertexes stored in the MD2 file are really unique, if not then you need to handle "merging" these same vertexes together.


Best Regards

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!