Sign in to follow this  

Split a triangle

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

Does this look right?
// ---------------------------------------------------------------------------- //
// Name		: SplitTriangle( )
// Desc		: Splits a triangle by a plane
// ---------------------------------------------------------------------------- //
INT_PTR __stdcall SplitTriangle( D3DXPLANE vPlane, D3DXVECTOR3 vPoints[ 3 ], TRIANGLE_LIST* pFront, TRIANGLE_LIST* pBack )
{
	stack<D3DXVECTOR3>				 vFront, vBack ;
	D3DXVECTOR3						 vIntersect ;
	TRIANGLE						 Triangle ;
	INT_PTR							 I, J, nClass ;

	// The first point, where is it?
	//
	switch ( ClassifyPoint( vPlane, vPoints[ 0 ] ) )
	{
	case D3DCLASS_BEHIND :
		 vFront.push( vPoints[ 0 ] ) ;
		 break ;

	case D3DCLASS_FRONT :
		 vBack.push(  vPoints[ 0 ] ) ;
		 break ;

	default :
		 vFront.push( vPoints[ 0 ] ) ;
		 vBack.push(  vPoints[ 0 ] ) ;
		 break ;
	}

	for ( I = 1 ; I < 3 ; I++ )
	{
		J							 = ( ( I < 2 ) ? ( I - 1 ) : 0 ) ;

		// Split!
		//
		if ( NULL != D3DXPlaneIntersectLine( &vIntersect, &vPlane, &vPoints[ J ], &vPoints[ I ] ) )
		{
			vFront.push( vPoints[ I ] ) ;
			 vBack.push( vPoints[ I ] ) ;
		}
		else
		{
			// Never mind then, just move on
			//
			switch ( ClassifyPoint( vPlane, vPoints[ I ] ) )
			{
			case D3DCLASS_BEHIND :
				 vFront.push( vPoints[ I ] ) ;
				 break ;

			case D3DCLASS_FRONT :
				 vBack.push(  vPoints[ I ] ) ;
				 break ;

			default :				 // <-- Just to be safe!
				 vFront.push( vPoints[ I ] ) ;
				 vBack.push(  vPoints[ I ] ) ;
				 break ;
			}
		}
	}

	// Push back list
	//
	if ( vBack.size( ) == 3 )		 // 1 Triangles
	{
		Triangle.vPoints[ 0 ]		 = vBack.top( ) ;
		vBack.pop( ) ;
		Triangle.vPoints[ 1 ]		 = vBack.top( ) ;
		vBack.pop( ) ;
		Triangle.vPoints[ 2 ]		 = vBack.top( ) ;
		vBack.pop( ) ;

		pBack->push( Triangle ) ;
	}
	else							 // 2 Triangles
	{
		// First triangle
		//
		Triangle.vPoints[ 0 ]		 = vBack.top( ) ;
		vBack.pop( ) ;
		Triangle.vPoints[ 1 ]		 = vBack.top( ) ;
		vBack.pop( ) ;
		Triangle.vPoints[ 2 ]		 = vBack.top( ) ;
		vBack.pop( ) ;
		pBack->push( Triangle ) ;

		// Swap, then get last vertex, push triangle
		//
		Triangle.vPoints[ 0 ]		 = Triangle.vPoints[ 1 ] ;
		Triangle.vPoints[ 1 ]		 = Triangle.vPoints[ 2 ] ;
		Triangle.vPoints[ 2 ]		 = vBack.top( ) ;
		vBack.pop( ) ;
		pBack->push( Triangle ) ;
	}

	// Push front list
	//
	if ( vFront.size( ) == 3 )		 // 1 Triangles
	{
		Triangle.vPoints[ 0 ]		 = vFront.top( ) ;
		vFront.pop( ) ;
		Triangle.vPoints[ 1 ]		 = vFront.top( ) ;
		vFront.pop( ) ;
		Triangle.vPoints[ 2 ]		 = vFront.top( ) ;
		vFront.pop( ) ;

		pBack->push( Triangle ) ;
	}
	else							 // 2 Triangles
	{
		// First triangle
		//
		Triangle.vPoints[ 0 ]		 = vFront.top( ) ;
		vFront.pop( ) ;
		Triangle.vPoints[ 1 ]		 = vFront.top( ) ;
		vFront.pop( ) ;
		Triangle.vPoints[ 2 ]		 = vFront.top( ) ;
		vFront.pop( ) ;
		pFront->push( Triangle ) ;

		// Swap, then get last vertex, push triangle
		//
		Triangle.vPoints[ 0 ]		 = Triangle.vPoints[ 1 ] ;
		Triangle.vPoints[ 1 ]		 = Triangle.vPoints[ 2 ] ;
		Triangle.vPoints[ 2 ]		 = vFront.top( ) ;
		vFront.pop( ) ;
		pFront->push( Triangle ) ;
	}

	return ( TRUE ) ;
}

The triangle is nothing more then an array of three D3DXVECTOR3 objects. I'm using std::stack for ease. Basically, the part I'm worried about is where the triangles are created. I don't know how to test this function, but before I put it to work, would you proof read it (so to speak) for me please? I figured I got the actual point separation down. I classify the first point in relation to the plane, then from there I test the line segments between two points in the triangle. I use the variable J as a sort of "previous" index. Hence, the little shortcut I use at the top of the for loop. If an intersection occurs, the D3DX function should return non NULL. This means, the "vIntersect" variable will be the intersection point. Then I just simple add that point to both front and back point lists. Simple right? The part I’m worried about is again, when the triangles are created. The code looks a little off, that’s one reason. Also, the order in which the vertices are specified, matters, as you all are aware of. I learned that I could test to see if each normal in the newly created polygons point the same was as the original. If they don’t, then flip them via reverse vertex order. But I [u]do not[/u] know how to test that. Please help if you can, I will be very great full.

Share this post


Link to post
Share on other sites
Quote:
Original post by sakky
Why does everyone look, but no one answers?
I wouldn't be discouraged by that - if you look at the average post, it will usually have many more views than replies.

Anyway, here's an idea. For me at least, examining someone else's code can take a lot of concentration, which can be hard to muster up, especially after looking at one's own code all day! :) Perhaps you could explain the problem in more detail, and/or post just the bits of code relevant to the problem. It's just a thought, but it might make it easier for people to help out.

Share this post


Link to post
Share on other sites
The part I'm owrried about is this-->


/* New Code !!! */

if ( vBack.size( ) == 3 )
{
Triangle.vPoints[ 0 ] = vBack.top( ) ; vBack.pop( ) ;
Triangle.vPoints[ 1 ] = vBack.top( ) ; vBack.pop( ) ;
Triangle.vPoints[ 2 ] = vBack.top( ) ; vBack.pop( ) ;

D3DXVec3Cross( &Triangle.vNormal,
&( Triangle.vPoints[ 0 ] - Triangle.vPoints[ 1 ] ),
&( Triangle.vPoints[ 0 ] - Triangle.vPoints[ 2 ] ) ) ;

if ( D3DXPlaneDotNormal( &vPlane, &Triangle.vNormal ) < 0.0F )
{
vTemp = Triangle.vPoints[ 0 ] ;
Triangle.vPoints[ 0 ] = Triangle.vPoints[ 2 ] ;
Triangle.vPoints[ 2 ] = vTemp ;
}

pBack->push_back( Triangle ) ;
}
else
{
Triangle.vPoints[ 0 ] = vBack.top( ) ; vBack.pop( ) ;
Triangle.vPoints[ 1 ] = vBack.top( ) ; vBack.pop( ) ;
Triangle.vPoints[ 2 ] = vBack.top( ) ; vBack.pop( ) ;

D3DXVec3Cross( &Triangle.vNormal,
&( Triangle.vPoints[ 0 ] - Triangle.vPoints[ 1 ] ),
&( Triangle.vPoints[ 0 ] - Triangle.vPoints[ 2 ] ) ) ;

if ( D3DXPlaneDotNormal( &vPlane, &Triangle.vNormal ) < 0.0F )
{
vTemp = Triangle.vPoints[ 0 ] ;
Triangle.vPoints[ 0 ] = Triangle.vPoints[ 2 ] ;
Triangle.vPoints[ 2 ] = vTemp ;
}

pBack->push_back( Triangle ) ;

Triangle.vPoints[ 0 ] = Triangle.vPoints[ 1 ] ;
Triangle.vPoints[ 1 ] = Triangle.vPoints[ 2 ] ;
Triangle.vPoints[ 2 ] = vBack.top( ) ; vBack.pop( ) ;

D3DXVec3Cross( &Triangle.vNormal,
&( Triangle.vPoints[ 0 ] - Triangle.vPoints[ 1 ] ),
&( Triangle.vPoints[ 0 ] - Triangle.vPoints[ 2 ] ) ) ;

if ( D3DXPlaneDotNormal( &vPlane, &Triangle.vNormal ) < 0.0F )
{
vTemp = Triangle.vPoints[ 0 ] ;
Triangle.vPoints[ 0 ] = Triangle.vPoints[ 2 ] ;
Triangle.vPoints[ 2 ] = vTemp ;
}

pBack->push_back( Triangle ) ;
}



A triangle (In my code) is nothing more then 4 D3DXVECTOR3 objects; 3 for position and 1 for normal. As I stated in the op, I believe I have the points taken care of. As in, I separate them into two lists: front & back. Any intersecting points I insert into both lists.

I'm just wondering if the polygon code is correct, and how I would get a texture coordinate with this also.

Share this post


Link to post
Share on other sites
Ok, I took a look at your original function. I may just be misunderstanding your code, but it doesn't like quite right to me. Have you tested it yet? Or are you just trying to get the theory down first? (Which is not a bad idea...)

The algorithm you're probably looking for is called 'Sutherland-Hodgman' clipping, and can also be used for splitting. It works for convex polygons with any number of sides. To get the correct results you have to process every edge, and you have to process them in order. In the simplest version of the algorithm, each edge is either fully in front of the plane, fully behind it, crossing it from front to back, or crossing it from back to front. Depending on which of these four categories the edge falls into, you intersect if required and add the appropriate points to the front and/or back polygon. If you do it right, both resulting polygons are wound correctly automatically.

Here is an example implementation. This is not the best or most robust way to do it, but it does illustrate the algorithm:


void SplitPolygon(
const std::vector<Vector3>& p, // Input polygon
std::vector<Vector3>& pf, // Front poly after split
std::vector<Vector3>& pb, // Back poly after split
const Vector3& n, // Plane normal
float d, // Plane distance (p.n = d)
float epsilon) // Tolerance for point-on-plane
{
if (p.empty()) {
return;
}

std::vector<float> dist(p.size());
std::vector<int> side(p.size());
int numFront = 0;
int numBack = 0;

enum {ON, FRONT, BACK, SPANNING};

for (int i = 0; i < p.size(); ++i) {
dist[i] = p[i].Dot(n) - d;
if (dist[i] > epsilon) {
side[i] = FRONT;
++numFront;
} else if (dist[i] < -epsilon) {
side[i] = BACK;
++numBack;
} else {
side[i] = ON;
}
}

pf.clear();
pb.clear();
if (!numBack) {
pf = p;
} else if (!numFront) {
pb = p;
} else {
for (int i = 0; i < p.size(); ++i) {
if (!(side[i] & BACK)) {
pf.push_back(p[i]);
}
if (!(side[i] & FRONT)) {
pb.push_back(p[i]);
}

int j = (i + 1) % p.size();
if ((side[i] | side[j]) == SPANNING) {
float t = dist[i] / (dist[i] - dist[j]);
Vector3 v = (1.0f - t) * p[i] + t * p[j];
pf.push_back(v);
pb.push_back(v);
}
}
}
}

Share this post


Link to post
Share on other sites
I'm using the split function for a BSP tree. I've seen the epsilon thing somewhere else before. So I guess it is no always good to use 0.0F for coinciding, okay then, I will change that.

You code is a little confusing, but oh well. Maybe that algorithm, I might be able to find information about it on Google then. Yes, I will search google for more information about it, thanks for the tip.

But I never thought I was using an algorithm. Just something I picked up from a book. I just loop through the points and add the points to front or back depending on the side they are on. If a point coincides with the splitter plane, I add the point to both front and back. Like wise, a point where an intersection lies is also added to both front and back.

I then check if the number of points in the front list is == 3. If it is, I create a polygon with those three points and flip it if it's normal is facing the wrong direction (i.e. other way of original polygon's normal). If the front point list has more then three points, I create two polygons with those four points. I use 0, 1, 2, then 1, 2 and 3. Then I do the same on the back point list.

I figured that there is an algorithm that, (as you said) done correctly will split the triangle with vertices all ready in order. So I won't have to waste time check for normal directions. Also, the part that I was really worried about was how I was creating the new triangles.

What I mean is how I create them off the indices in the point lists. It just seamed a little odd to me. I figured the dot product will tell me if the normal from a polygon and the original will tell me if it's facing the right way (i.e. > 0.0F or epsilon). So then, as long as I get all the points into a polygon, then I should be safe.

The splitter function and a traversal function of the BSP are the only that confuse me. The splitter most. But BSP is not the topic and this type of functionality I want to use else were too. So that being said, the input polygon will always be a triangle. The output polygons must be lists of polygons separated by the clipping (or splitter if you will) plane.

Please keep in mind the reason why I reiterate so much of what you probably all ready know is so that A) I can make sure I know it and B) you know that I know it.

Share this post


Link to post
Share on other sites
Quote:
Original post by sakky
Please keep in mind the reason why I reiterate so much of what you probably all ready know is so that A) I can make sure I know it and B) you know that I know it.
Sure, I understand :) As to your original function, I'd have to analyze it more carefully to be sure of this, but it still doesn't look right to me. For one thing, it looks like you're only processing two of the triangle edges; also it seems the endpoint order is not consistent from edge to edge. But perhaps closer inspection would show that it's just a different but equally valid way of doing it...

Nonetheless, I can *guarantee* that the Sutherland-Hodgman method works, so it might be worth pursuing. The code I posted might be a little confusing due to some little tricks and shortcuts, but it's a straightforward implementation that I know works. The only shortcoming of that code is that it doesn't incorporate an extension to the algorithm that makes it a little more robust. Although I have a robust version of this implemented for polygon clipping, I don't have an implementation at the moment for splitting, otherwise I'd post it.

Also, if you can afford a book, Christer Ericson's 'Real-Time Collision Detection' has good coverage of robust polygon splitting, particularly as it applies to BSP construction and spatial partitioning.

Share this post


Link to post
Share on other sites
I’ve broken my entire algorithm and structure into two separate classes: CVertex and CTriangle. Both classes define basic functionality such as parameterized and copy constructors. Plus I encapsulate a little bit of C++’s operator overloading functionality for an assignment and two equality operators (i.e. == and !=). They also have a set function and I also made their data members public. This is so I don’t have to make lots of get and set functions; only a few. I can use the class’s own functionality in many different circumstances like defining arrays and what not.

So my vertex class defines two function of most importance: lerp and class. Class (short for classify) is for classifying the vertex’s position in relation to a plane. I might add in triangle support, but I would like to limit the math on computing a plane. A vertex can only be one of the following: in-front, coincide or in-back of a plane.

The "Lerp" function is what I use to determine a linear interpolated vertex between two specified ones in relation to time (of course). Now, I want to have two overloaded functions; one taking a FLOAT as parameter and the other taking a D3DXVECTOR3 as parameter. The reason for this is simple, I figured that when a polygon’s(triangle in my case) edge is split, the intersection point is similar to linear interpolation. What I mean is, I can compute the values for position, color and texture coordinates using the intersection point’s magnitude as time value. If there is a better, as in more accurate way to achieve this, please let me know.

The triangle class is pretty much an array vector of the vertex class. In the old post, I use an array of pointers as indices instead of unsigned shorts. Then, I used a union of both types and specified a flag and global method that changes between the two. I think that the pointer indices have got to go because that could jus cause to much problems and already I’m running into problems with using them. The triangle also has some other data members for things such as texture and/or material flags and identifiers, but nothing to complex. Oh, it also has a normal that I compute from the cross product of the three points.

My biggest worry is to make sure the when I’m splitting a triangle that the intersecting vertices [u]must have correct values[/u] for their position. My next worry would be making sure that all the vertices are used to make triangles, and that none are reused in such as way that triangle overlap each other. Other then this, I really have no worries because if I get a triangle’s vertices in the wrong order, I can flip it via swapping the first and last index’s values.

So, I looked a little bit on Google for the said algorithm you mentioned. I found some information (lots actually), but was unable to read it because I have many other things to do. But, I will later. In the mean time, could to give a few tips and correct me if I’m wrong in how I compute the values of a intersecting vertex. Also, I use the D3DXPlaneIntersectLine function for checking intersections via return value.

No I think, I pretty much explained my entire program to you now.

Share this post


Link to post
Share on other sites
That's a very clear explanation. I don't have much to add, but here are a few notes:

1. Yes, I think you can use your lerp function for finding the vertex values (position, texcoord, and so on) for the intersection point. I'm not positive about this, but I don't see why that wouldn't be the case.

2. One thing about using the DirectX intersection function for your splitting is that the same information is essentially computed twice, once when the points are classified, and once in the intersection function. If you look at the code I posted you'll see that the parametric value for the intersection is actually computed using the same values that were used to classify the point. If nothing else, this approach is a bit more efficient.

3. This may be irrelevant (and you may already be aware of it), but I'll just point out that polygon splitting in general is kind of pain, and I don't think is done that much anymore. Typically, tree nodes or leaves store references to the polygons that they touch, but the polygons themselves are left intact.

4. If you can't get Christer's book (and if you have access to PowerPoint), you might look at the first hit on this page. It touches on some of the issues involved in polygon splitting, including how to avoid concave polygons, T-junctions, and other artifacts. It's definitely worth a look if your goal is a flexible and robust triangle or polygon splitter.

Share this post


Link to post
Share on other sites
That is the case for me. But I never thought that I could be able to use the dot product as time in the interpolation equation. I mean, it makes total sense, but I never thought of it. That little trick could like, rip lots of code out of my code I have now. Because I use an interpolation value over and over again with dot and intersection points, it makes total sense to use it.

I often wondered if I should split a polygon or not. It does have it’s uses if you wanted an explosion sprite to correctly wrap around complex geometry I guess. But I use to think that if I were to build a BSP, Quad or Oct-tree, that I would just push a polygon into both lists if it is spanning. And or, use another list that contains spanning polygons. So if poly splitting isn’t really done any more and there are ways to get similar balanced trees, then why should I do it?

Hmm... thanks for all you information. You’ve helped me out quite a lot!

Share this post


Link to post
Share on other sites
Polygon splitting is still used for modern applications, although it IS a pain and performance unfriendly in large doses. So there are a few tricks to help avoid them such as actually moving a split-plane in order to avoid/minimise splitting.
For more infos on this check out loose-octrees and ABTs (Adaptive Binary Trees) - There are similar but the plane is always axis aligned (easy to implement) and can be pushed about to minimise splitting (optimisation).

For my splitting algo I use an optimised verson of the sutherland-hodgeman method that addresses the issue jyk mentioned in his second point about redundant data.

As for your code, I don't have time to proof read but I would personally use a std::deque as IIRC it is faster for repetitive growth (adding new vertices) than a std::vector or std::stack.

good luck :)

Share this post


Link to post
Share on other sites
Quote:
Original post by sakky
I often wondered if I should split a polygon or not. It does have it’s uses if you wanted an explosion sprite to correctly wrap around complex geometry I guess.
Just wanted to mention that you've highlighted a place where clipping (as opposed to splitting) is quite useful. Assuming that you're talking about decals here, the method of clipping mesh geometry to a decal volume (as detailed in Eric Lengyel's GPG article) is very effective and produces great results. So it's certainly useful to have a good clipping function at least. Just to give you some more reference material, here's the clipping function I'm using currently, which I've tested informally and I believe to be robust, given an appropriate epsilon. It actually works for both 2d and 3d (N is the template dimension parameter), but you could easily strip out all the template stuff and make a 3d-only version:


namespace jyk {
namespace Clipping {

enum {ON, BACK, FRONT, SPANNING};

template <typename T, int N>
int ClassifyPointToPlane(
const cml::vector< T,cml::fixed<N> >& point,
const cml::vector< T,cml::fixed<N> >& normal, // Must be normalized
T distance,
T& dist,
T epsilon)
{
dist = cml::dot(point,normal)-distance;
return dist < -epsilon ? BACK : (dist > epsilon ? FRONT : ON);
}

template <typename T, int N>
bool PolygonToHPlane(
const cml::vector< T,cml::fixed<N> >* const inVerts,
int numInVerts,
cml::vector< T,cml::fixed<N> >* const outVerts,
int& numOutVerts,
int maxNumOutVerts,
const cml::vector< T,cml::fixed<N> >& normal, // Must be normalized
T distance,
T epsilon)
{
typedef cml::vector< T,cml::fixed<N> > vector_type;

vector_type p0 = inVerts[numInVerts-1];
T dist0;
int side0 = ClassifyPointToPlane(p0, normal, distance, dist0, epsilon);

numOutVerts = 0;
for (int i = 0; i < numInVerts; ++i) {
vector_type p1 = inVerts[i];
T dist1;
int side1 = ClassifyPointToPlane(p1, normal, distance, dist1, epsilon);

if ((side0 | side1) == SPANNING) {
if (numOutVerts == maxNumOutVerts) {
Log::Get()->Print("Max number of verts exceeded in Clipping::PolygonToHPlane()!");
numOutVerts = 0;
return false;
}
outVerts[numOutVerts++] = p0+(dist0/(dist0-dist1))*(p1-p0);
}
if (side1 != BACK) {
if (numOutVerts == maxNumOutVerts) {
Log::Get()->Print("Max number of verts exceeded in Clipping::PolygonToHPlane()!");
numOutVerts = 0;
return false;
}
outVerts[numOutVerts++] = p1;
}

p0 = p1;
dist0 = dist1;
side0 = side1;
}

return numOutVerts > 0;
}

} // namespace Clipping
} // namespace jyk

Share this post


Link to post
Share on other sites

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