// ---------------------------------------------------------------------------- //
// 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 ) )
{
vFront.push( vPoints ) ;
vBack.push( vPoints ) ;
}
<span class="cpp-keyword">else</span>
{
<span class="cpp-comment">// Never mind then, just move on</span>
<span class="cpp-comment">//</span>
<span class="cpp-keyword">switch</span> ( ClassifyPoint( vPlane, vPoints ) )
{
<span class="cpp-keyword">case</span> D3DCLASS_BEHIND :
vFront.push( vPoints ) ;
<span class="cpp-keyword">break</span> ;
<span class="cpp-keyword">case</span> D3DCLASS_FRONT :
vBack.push( vPoints ) ;
<span class="cpp-keyword">break</span> ;
<span class="cpp-keyword">default</span> : <span class="cpp-comment">// <– Just to be safe!</span>
vFront.push( vPoints ) ;
vBack.push( vPoints ) ;
<span class="cpp-keyword">break</span> ;
}
}
}
<span class="cpp-comment">// Push back list</span>
<span class="cpp-comment">//</span>
<span class="cpp-keyword">if</span> ( vBack.size( ) == <span class="cpp-number">3</span> ) <span class="cpp-comment">// 1 Triangles</span>
{
Triangle.vPoints[ <span class="cpp-number">0</span> ] = vBack.top( ) ;
vBack.pop( ) ;
Triangle.vPoints[ <span class="cpp-number">1</span> ] = vBack.top( ) ;
vBack.pop( ) ;
Triangle.vPoints[ <span class="cpp-number">2</span> ] = vBack.top( ) ;
vBack.pop( ) ;
pBack->push( Triangle ) ;
}
<span class="cpp-keyword">else</span> <span class="cpp-comment">// 2 Triangles</span>
{
<span class="cpp-comment">// First triangle</span>
<span class="cpp-comment">//</span>
Triangle.vPoints[ <span class="cpp-number">0</span> ] = vBack.top( ) ;
vBack.pop( ) ;
Triangle.vPoints[ <span class="cpp-number">1</span> ] = vBack.top( ) ;
vBack.pop( ) ;
Triangle.vPoints[ <span class="cpp-number">2</span> ] = vBack.top( ) ;
vBack.pop( ) ;
pBack->push( Triangle ) ;
<span class="cpp-comment">// Swap, then get last vertex, push triangle</span>
<span class="cpp-comment">//</span>
Triangle.vPoints[ <span class="cpp-number">0</span> ] = Triangle.vPoints[ <span class="cpp-number">1</span> ] ;
Triangle.vPoints[ <span class="cpp-number">1</span> ] = Triangle.vPoints[ <span class="cpp-number">2</span> ] ;
Triangle.vPoints[ <span class="cpp-number">2</span> ] = vBack.top( ) ;
vBack.pop( ) ;
pBack->push( Triangle ) ;
}
<span class="cpp-comment">// Push front list</span>
<span class="cpp-comment">//</span>
<span class="cpp-keyword">if</span> ( vFront.size( ) == <span class="cpp-number">3</span> ) <span class="cpp-comment">// 1 Triangles</span>
{
Triangle.vPoints[ <span class="cpp-number">0</span> ] = vFront.top( ) ;
vFront.pop( ) ;
Triangle.vPoints[ <span class="cpp-number">1</span> ] = vFront.top( ) ;
vFront.pop( ) ;
Triangle.vPoints[ <span class="cpp-number">2</span> ] = vFront.top( ) ;
vFront.pop( ) ;
pBack->push( Triangle ) ;
}
<span class="cpp-keyword">else</span> <span class="cpp-comment">// 2 Triangles</span>
{
<span class="cpp-comment">// First triangle</span>
<span class="cpp-comment">//</span>
Triangle.vPoints[ <span class="cpp-number">0</span> ] = vFront.top( ) ;
vFront.pop( ) ;
Triangle.vPoints[ <span class="cpp-number">1</span> ] = vFront.top( ) ;
vFront.pop( ) ;
Triangle.vPoints[ <span class="cpp-number">2</span> ] = vFront.top( ) ;
vFront.pop( ) ;
pFront->push( Triangle ) ;
<span class="cpp-comment">// Swap, then get last vertex, push triangle</span>
<span class="cpp-comment">//</span>
Triangle.vPoints[ <span class="cpp-number">0</span> ] = Triangle.vPoints[ <span class="cpp-number">1</span> ] ;
Triangle.vPoints[ <span class="cpp-number">1</span> ] = Triangle.vPoints[ <span class="cpp-number">2</span> ] ;
Triangle.vPoints[ <span class="cpp-number">2</span> ] = vFront.top( ) ;
vFront.pop( ) ;
pFront->push( Triangle ) ;
}
<span class="cpp-keyword">return</span> ( <span class="cpp-keyword">TRUE</span> ) ;
}
</pre></div><!–ENDSCRIPT–>
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 <span style="text-decoration:underline;">do not</span> know how to test that.
Please help if you can, I will be very great full.
Split a triangle
Author
Does this look right?
Quote:Original post by sakkyI wouldn't be discouraged by that - if you look at the average post, it will usually have many more views than replies.
Why does everyone look, but no one answers?
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.
Author
The part I'm owrried about is this-->
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.
/* 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.
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:
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 = p.Dot(n) - d; if (dist > epsilon) { side = FRONT; ++numFront; } else if (dist < -epsilon) { side = BACK; ++numBack; } else { side = 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 & BACK)) { pf.push_back(p); } if (!(side & FRONT)) { pb.push_back(p); } int j = (i + 1) % p.size(); if ((side | side[j]) == SPANNING) { float t = dist / (dist - dist[j]); Vector3 v = (1.0f - t) * p + t * p[j]; pf.push_back(v); pb.push_back(v); } } }}
Author
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.
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.
Quote:Original post by sakkySure, 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...
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.
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.
Author
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 must have correct values 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.
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 must have correct values 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.
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.
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.
Author
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!
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!
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
