# [C#] Problem with triangle clipping algortihm and duplicate vertices.

## Recommended Posts

Spa8nky    230
If I wish to clip a triangle to 6 planes then I understand that the process should be: 1) Clip triangle to plane 1 and return clipped vertices. 2) Clip the result of 1) to plane 2 and return clipped vertices 3) Repeat for all other planes The problem is that my algorithm is producing duplicate vertices. This occurs because the vertices that are behind the clipping plane are added to the list of clipped vertices so they can be tested with the next clipping plane. How can I avoid this from happening and still be able to test correctly? My current algorithm is as follows:
            Vector3[] v_ToClip = new Vector3[3];

v_ToClip[0] = Screen_Game.debug_Triangle[0].GetVertex(0);
v_ToClip[1] = Screen_Game.debug_Triangle[0].GetVertex(1);
v_ToClip[2] = Screen_Game.debug_Triangle[0].GetVertex(2);

List<Vector3> v_Clipped = new List<Vector3>(100);

for (int i = 0; i < 6; ++i)
{
// Clip vertices to current
ClipVerticesToPlane(planes[i], ref v_Clipped, v_ToClip);

// Set the new vertices to clip using the clipped vertices
v_ToClip = v_Clipped.ToArray();
}

/// <summary>
/// Clip a set of CCW ordered vertices to a plane
/// </summary>
/// <param name="plane">Plane used to clip vertices</param>
/// <param name="vertices_Clipped">Clipped vertex points</param>
/// <param name="vertices">Vertices to clip to plane (ordered CCW)</param>
private void ClipVerticesToPlane(CD_Plane plane, ref List<Vector3> vertices_Clipped, params Vector3[] vertices)
{
// Test all edges (a, b) starting with edge from last to first vertex
int numVertices = vertices.Length;
Vector3 a = vertices[numVertices - 1];
bool a_Side = PointBehindPlane(a, plane);

// Loop over all edges given by vertex pair (n - 1, n)
for (int n = 0; n < numVertices; ++n)
{
Vector3 b = vertices[n];
bool b_Side = PointBehindPlane(b, plane);

// Point is in front of plane
if (!b_Side)
{
if (a_Side)
{
// Edge (a, b) straddles plane, output intersection point
Vector3 i = IntersectSegmentPlane(b, a, plane);
//vertices_Clipped[vertices_Count++] = i;
}
}
// Point is behind plane
else
{
if (!a_Side)
{
// Edge (a, b) straddles plane, output intersection point
Vector3 i = IntersectSegmentPlane(a, b, plane);
//vertices_Clipped[vertices_Count++] = i;
}

// In all cases, output b to the back side
//vertices_Clipped[vertices_Count++] = b;
}

// Keep b as the starting point of the next edge
a = b;
a_Side = b_Side;
}
}


Thank you. [Edited by - Spa8nky on March 12, 2010 2:45:06 PM]

##### Share on other sites
Spa8nky    230
If I change my for loop to:

            for (int i = 0; i < 6; ++i)            {                          v_Clipped.Clear();                // Clip vertices to current                ClipVerticesToPlane(planes[i], ref v_Clipped, v_ToClip);                // Set the new vertices to clip using the clipped vertices                v_ToClip = v_Clipped.ToArray();            }

Then everything works ok. Can anyone suggest a more elegant way of doing the above?

Thanks again.

EDIT:

I've done away with lists and now only use arrays:

            // Holds all vertices that have been clipped behind each plane tested            Vector3[] v_Clipped = new Vector3[1];            int v_Count = 0;            for (int i = 0; i < 6; ++i)            {                          // Clip vertices to current                v_Clipped = ClipVerticesToPlane(planes[i], v_ToClip);                // Set the new vertices to clip using the clipped vertices                if (v_Clipped != null)                {                    v_ToClip = v_Clipped;                }                else                {                    vertices = new VertexPositionTexture[0];                    return;                }            }            v_Count = v_Clipped.Length;            // Create decal vertices from clipped vertices            vertices = new VertexPositionTexture[v_Count];.....        /// <summary>        /// Clip a set of CCW ordered vertices to a plane        /// </summary>        /// <param name="plane">Plane used to clip vertices</param>        /// <param name="vertices_Clipped">Clipped vertex points</param>        /// <param name="vertices">Vertices to clip to plane (ordered CCW)</param>        private Vector3[] ClipVerticesToPlane(CD_Plane plane, params Vector3[] vertices)        {            Vector3[] vertices_Clipped = new Vector3[25];            int vertices_Count = 0;            // Test all edges (a, b) starting with edge from last to first vertex            int numVertices = vertices.Length;            if (numVertices == 0)            {                return null;            }            Vector3 a = vertices[numVertices - 1];            bool a_Side = PointBehindPlane(a, plane);            // Loop over all edges given by vertex pair (n - 1, n)            for (int n = 0; n < numVertices; ++n)            {                Vector3 b = vertices[n];                bool b_Side = PointBehindPlane(b, plane);                // Point is in front of plane                if (!b_Side)                {                    if (a_Side)                    {                        // Edge (a, b) straddles plane, output intersection point                        Vector3 i = IntersectSegmentPlane(b, a, plane);                        vertices_Clipped[vertices_Count++] = i;                    }                }                // Point is behind plane                else                {                    if (!a_Side)                    {                        // Edge (a, b) straddles plane, output intersection point                        Vector3 i = IntersectSegmentPlane(a, b, plane);                        vertices_Clipped[vertices_Count++] = i;                    }                    // In all cases, output b to the back side                    vertices_Clipped[vertices_Count++] = b;                }                // Keep b as the starting point of the next edge                a = b;                a_Side = b_Side;            }            Vector3[] v = new Vector3[vertices_Count];            for (int i = 0; i < vertices_Count; ++i)            {                v[i] = vertices_Clipped[i];            }            return v;        }

Any comments on the code would be welcome.

[Edited by - Spa8nky on March 12, 2010 3:57:54 PM]