Sign in to follow this  

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

This topic is 2836 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

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;
                        vertices_Clipped.Add(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;
                        vertices_Clipped.Add(i);
                    }

                    // In all cases, output b to the back side
                    //vertices_Clipped[vertices_Count++] = b;
                    vertices_Clipped.Add(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 this post


Link to post
Share on other sites
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]

Share this post


Link to post
Share on other sites

This topic is 2836 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.

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