Original Post
I've implemented an importer for the .3DS file format using XNA. I'm currently implementing shadow volumes but I've run into some problems. I had to rebuild the entire trimesh in code to build a degenerate model for the shadow extrusion, which proved to give me some problems, as you can see in the picture here Can anyone figure out what's going on? It's flickering btw when running. The code used to build the degenerate trimesh is show below: It is also important to notice it only does this on really complex models. The models should be closed. I really do hope someone will help me out.
public struct EdgesComparer
{
public Vector3 a;
public Vector3 b;
public int face1;
public int face2;
}
public struct ShadowVertex
{
public Vector3 Position;
public Vector3 Normal;
public const int Size = 12 + 12;
public static VertexElement[] Elements =
{
new VertexElement(0, 0, VertexElementFormat.Vector3, VertexElementMethod.Default, VertexElementUsage.Position, 0),
new VertexElement(0, 12, VertexElementFormat.Vector3, VertexElementMethod.Default, VertexElementUsage.Normal, 0),
};
}
public class ShadowVolume
{
// Mesh that contains the shadow volume
private Mesh m_mesh;
private int m_numVertices;
private ShadowVertex[] m_vertices;
private int m_numIndices;
private short[] m_indices;
private int m_numFaces;
private int m_numEdges;
private EdgesComparer[] m_edges;
// Used to map face index with a normal
private Dictionary<int, Vector3> m_faceNormals;
// Used to keep track of added faces
private Dictionary<int, bool> m_faceHash;
public ShadowVolume(Mesh mesh)
{
m_mesh = mesh;
m_numFaces = m_mesh.Faces.Length;
// Max final vertices:
// Number of faces * 3
m_numVertices = 0;
m_vertices = new ShadowVertex[m_numFaces * 3];
// Max final faces:
// (numfaces * 3) + ((numfaces * 3 * 3) * 2)
m_numIndices = 0;
m_indices = new short[(m_numFaces * 3) + ((m_numFaces * 3 * 3)*2)];
m_numEdges = 0;
m_edges = new EdgesComparer[m_numFaces * 3];
m_faceNormals = new Dictionary<int, Vector3>();
m_faceHash = new Dictionary<int, bool>();
}
public void Build()
{
// Build the volume
ShadowVertex v0, v1, v2, v3;
// For ease of access
MeshVertex[] vertices = m_mesh.Vertices;
for (int i = 0; i < m_numFaces; i++)
{
Face3DS indices = m_mesh.Faces;
// Find the face vertices
v0.Position = vertices[(int)indices.A].Position;
v1.Position = vertices[(int)indices.B].Position;
v2.Position = vertices[(int)indices.C].Position;
// Calculate the face normal
Vector3 cross1 = (v1.Position - v0.Position);
Vector3 cross2 = (v2.Position - v1.Position);
Vector3 normal = Vector3.Cross(cross1, cross2);
normal.Normalize();
// Save the face information
m_faceNormals.Add(i, normal);
m_faceHash.Add(i, false);
// Insert the edge in the map
InsertEdge(v0.Position, v1.Position, i);
InsertEdge(v1.Position, v2.Position, i);
InsertEdge(v2.Position, v0.Position, i);
}
// For each unique edge, duplicate it to create the degenerate geometry.
for (int i = 0; i < m_numEdges; i++)
{
EdgesComparer edge = m_edges;
// Add the faces if they have not yet been added
if (!m_faceHash[edge.face1])
InsertFace(edge.face1);
if (!m_faceHash[edge.face2])
InsertFace(edge.face2);
// Add the degenerate quad indices
v0.Position = edge.a;
v0.Normal = m_faceNormals[edge.face1];
v1.Position = edge.b;
v1.Normal = m_faceNormals[edge.face1];
v2.Position = edge.a;
v2.Normal = m_faceNormals[edge.face2];
v3.Position = edge.b;
v3.Normal = m_faceNormals[edge.face2];
short i0 = -1, i1 = -1, i2 = -1, i3 = -1;
// Find the vertices and use the index
for (short j = 0; j < m_numVertices; j++)
{
// Find first index
if (v0.Position == m_vertices[j].Position &&
v0.Normal == m_vertices[j].Normal)
i0 = j;
// Find second index
if (v1.Position == m_vertices[j].Position &&
v1.Normal == m_vertices[j].Normal)
i1 = j;
// Find third index
if (v2.Position == m_vertices[j].Position &&
v2.Normal == m_vertices[j].Normal)
i2 = j;
// Find forth index
if (v3.Position == m_vertices[j].Position &&
v3.Normal == m_vertices[j].Normal)
i3 = j;
}
// Add vertices and indices
m_indices[m_numIndices++] = i0;
m_indices[m_numIndices++] = i2;
m_indices[m_numIndices++] = i1;
m_indices[m_numIndices++] = i3;
m_indices[m_numIndices++] = i1;
m_indices[m_numIndices++] = i2;
}
}
private void InsertEdge(Vector3 a, Vector3 b, int face)
{
bool found = false;
// If the edge is there already
for (int i = 0; i < m_edges.Length; i++)
{
// Edge found
if ((m_edges.a == a && m_edges.b == b) ||
(m_edges.a == b && m_edges.b == a))
{
m_edges.face2 = face; // An edge can only share two edges
found = true;
break;
}
}
// Edge NOT found - Insert new
if (!found)
{
m_edges[m_numEdges].a = a;
m_edges[m_numEdges].b = b;
m_edges[m_numEdges].face1 = face;
m_numEdges++;
}
}
private void InsertFace(int face)
{
Face3DS indices = m_mesh.Faces[face];
// For ease of access
MeshVertex[] vertices = m_mesh.Vertices;
ShadowVertex v0, v1, v2;
short i0 = -1, i1 = -1, i2 = -1;
// Add the face vertices
v0.Position = vertices[(int)indices.A].Position;
v0.Normal = m_faceNormals[face];
v1.Position = vertices[(int)indices.B].Position;
v1.Normal = m_faceNormals[face];
v2.Position = vertices[(int)indices.C].Position;
v2.Normal = m_faceNormals[face];
// Find if vertices already exist
for (int j = 0; j < m_numVertices; j++)
{
// Find first index
if (v0.Position == m_vertices[j].Position &&
v0.Normal == m_vertices[j].Normal)
i0 = Convert.ToInt16(j);
// Find second index
if (v1.Position == m_vertices[j].Position &&
v1.Normal == m_vertices[j].Normal)
i1 = Convert.ToInt16(j);
// Find third index
if (v2.Position == m_vertices[j].Position &&
v2.Normal == m_vertices[j].Normal)
i2 = Convert.ToInt16(j);
}
// Add vertices and indices
if (i0 != -1)
m_indices[m_numIndices++] = i0; // Point to existing vertex
else
{
m_indices[m_numIndices++] = Convert.ToInt16(m_numVertices);
m_vertices[m_numVertices++] = v0;
}
if (i1 != -1)
m_indices[m_numIndices++] = i1; // Point to existing vertex
else
{
m_indices[m_numIndices++] = Convert.ToInt16(m_numVertices);
m_vertices[m_numVertices++] = v1;
}
if (i2 != -1)
m_indices[m_numIndices++] = i2; // Point to existing vertex
else
{
m_indices[m_numIndices++] = Convert.ToInt16(m_numVertices);
m_vertices[m_numVertices++] = v2;
}
// Indicate that the face has been added
m_faceHash[face] = true;
}
}
}