Sign in to follow this  
Psyian

Splitting triangles

Recommended Posts

Hi all, Right ive tried looking on google and these forums, but i still dont get it. Nothing works. I think i need it explained to me at the simplest possible level. Duh McFly.... Anyhow, ive got my octree working nicely but know i need to split up some triangles so they fit in all snug. How can you split triangles up, i think i can handle the splitting of 1 triangle but how do u accomodate for more, where triangles are adjacent. I've tried it out on paper and nothing, dont get it. If anyone could help us out / give me a link, i'll bear their children, this has been bugging me for a while. I even stopped work on it to create a skybox, now thats done i need to sort it. Thanks in advance Psy

Share this post


Link to post
Share on other sites
You can split triangles independently of other triangles in the scene. Simply process the triangles in any order, splitting them when necessary and putting them (or their halves) into the correct box.

Splitting a triangle is fairly easy (as is splitting any convex polygon): simply run along its edges, remembering what side of the splitting plane each vertex lies. Whenever you change sides, create a new vertex at the point of intersection. Then simply build the two new polygons by inserting the two points of intersection at the correct locations. Just pay attention to vertices that are ON the plane, you must handle them separately.

Share this post


Link to post
Share on other sites

Cheers for replying dude, sorry i havent had a chance to reply for a while. From what you say, it seems quite simple, but i have tried working it out, and still dont get it, might have to sit down and give it a couple of hrs. Wish i could discuss this properly, but i'm going on holiday in a matter of hours, good old portugal for two weeks. Yey!!!!!! I'll either repost when i get back, or if you have your email address on here i'll contact you directly. Well, thats if you dont mind.

Anyway must be getting on. Don't wanna miss the flight!!!
Thanks again!


Share this post


Link to post
Share on other sites
I had the same problem as you a while back when doing BSP Trees, basically it is much much easier NOT to deal in triangles. When you are constructing your Octree use n-sided polygons. So basically a structure that stores a list of verticies (or indicies to verticies) when you first load the model that you are going to process into your octree, all the polygons will have 3 points (i.e. just triangles) now when you come to split a polygon things are very simple.

look at this: BSP FAQ specifically the "HOW DO YOU PARTITION A POLYGON WITH A PLANE?" section. The pseudo C++, although probably one of the wrost languages to write pseudo code in, explains how to split a polygon. Basically you run around the edge of the polygon and see if any two points that form an edge are on opposite sides of your dividing plane, if they are then you take the intersection point between the two points and the plane as a new point in both your polygons. Note that you will always get two polygons when splitting a polygon across a plane, one that is infront and one that is behind the plane.

Ah! But you are thinking, wait a second my engine needs things in triangles NOT polygons? What good is this to me? Well as it happens it is VERY easy to turn the polygons into triangles using a fanning technique. As long as you have constructed your split polygons exactly like that pseudo C++ example things will go smoothly. Here is my C# code for converting a polygon into triangles:


public Triangle[] Convert(Polygon polygon)
{
ArrayList triangles = new ArrayList(polygon.Points.Count);

for (int i = 2; i < polygon.Points.Count; i++)
{
// Create the triangles like a triangle fan
Triangle triangle = new Triangle(
polygon.Points[0], polygon.Points[i-1], plygon.Points[i]);

triangles.Add(triangle);
}

return (Triangle[]) triangles.ToArray(typeof(Triangle));
}





Also here is my polygon splitting code in C#, which might be easier for you to understand, note that I have also made the split preserve the texture coordinates of the verticies, should you need them by working out how far along the edge the split had occured as a proportion of the total edge length:


/// <summary>
/// Creates a new vertex where a vertex intersects a plane
/// </summary>
/// <param name="divider">The plane dividing the vertex</param>
/// <param name="start">Where the vertex to be split starts</param>
/// <param name="end">Where the vertex to be split ends</param>
/// <returns>The index in the vertex buffer of the new vertex</returns>
private ushort SplitVertex(Plane divider, VertexPNT start, VertexPNT end)
{
// The new vertex is calculated by the intersection on the plane
Vector3 middle = Plane.IntersectLine(divider, start.Position, end.Position);

// we need to know how far along the old vertex the new is
float proportion = (start.Position - middle).Length() / (start.Position - end.Position).Length();

// and assign the new texture UV coordinates to the new vertex
float Tu = start.Tu + (end.Tu - start.Tu) * proportion;
float Tv = start.Tv + (end.Tv - start.Tv) * proportion;

// add the new vertex the verticies array and return its index
return (ushort) m_Verticies.Add(new VertexPNT(middle, start.Normal, Tu, Tv));

}

/// <summary>
/// Splits a polygon that spans a divider
/// </summary>
private SplitPolygon SplitPolygon(Plane divider, Polygon polygon)
{
Polygon front = new Polygon();
Polygon back = new Polygon();

int count = polygon.Points.Count;

VertexPNT pointA;
VertexPNT pointB;

Side sideA;
Side sideB;

pointA = (VertexPNT) m_Verticies[polygon.Points[count-1]];
sideA = SpacePartition.ClassifyPoint(divider, pointA.Position, Epsilon);

for (int i = 0; i < count; i++)
{
pointB = (VertexPNT) m_Verticies[polygon.Points[i]];
sideB = SpacePartition.ClassifyPoint(divider, pointB.Position, Epsilon);

if (sideB == Side.Infront)
{
if (sideA == Side.Behind)
{
// Create a new point at the intersection and add it
// to both the front and back polygons
ushort index = SplitVertex(divider, pointA, pointB);
front.Points.Add(index);
back.Points.Add(index);
}

front.Points.Add(polygon.Points[i]);
}
else if (sideB == Side.Behind)
{
if (sideA == Side.Infront)
{
// Create a new point at the intersection and add it
// to both the front and back polygons
ushort index = SplitVertex(divider, pointA, pointB);
front.Points.Add(index);
back.Points.Add(index);
}
back.Points.Add(polygon.Points[i]);
}
else
{
// The point coincides with the plane, so add it
// to the front and the back
front.Points.Add(polygon.Points[i]);
back.Points.Add(polygon.Points[i]);
}

// Use this point as the next point to test
pointA = pointB;
sideA = sideB;
}

return new SplitPolygon(front, back);
}






In the above source a VertexPNT is a struct with position, normal and texture coordinate data. m_Verticies is an array of verticies that I am indexing with unsigned shorts. So in my example, my polygon structures are storing indicies to verticies in my m_Verticies array. When I split and edge, it returns the index of the new vertex in the m_Verticies array. Of course you can just work directly with the verticies in your polygon if you want.

I recommend that you use the code as a guide and write you own methods otherwise you will run into trouble if you don't understand what is going on. I find it a great help to draw on a bit of paper the splitting of polygons etc by just drawing an n-sideded polygon or triangle and then just slapping a line randomly through it and examining what two peices will be left. You should step through the splitting code for a simple split test and see how it works, it's quite smart in its simplicity.

Good luck, any questions just ask.

Oh, btw my Polygon is just a struct containing and array of unsigned shorts that I grow if I need more points.

Share this post


Link to post
Share on other sites

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