Polygon Clipping
Author
I'm looking for an algorithm for polygon clipping. My case is like this:
An "outer polygon" with N-vertices (could be concave). And 1 or more inner polygons of m-vertices. The second set of polygons are guaranteed to be inside the outer boundary. Now, I need an algorithm that can create a triangle mesh of all the faces that should be on the clipped polygon.
ANybody knows something like this?
Am I correct when I state that you're actually cutting a hole in a convex/concave face?
In that case you could first tesselate the outer into triangles, the hole into triangles and then clip the outer by the inner.
Cheers
In that case you could first tesselate the outer into triangles, the hole into triangles and then clip the outer by the inner.
Cheers
You might want to clarify your question a bit.
But if I understand it correctly you could do this in OpenGL.
This is from www.opengl.org
Polygon Tessellation
The polygon tessellation routines triangulate a concave polygon with one or more contours. To use this GLU feature, first create a tessellation object with gluNewTess(), and define callback routines that will be used to process the triangles generated by the tessellator (with gluTessCallBack()). Then use gluBeginPolygon(), gluTessVertex(), gluNextContour(), and gluEndPolygon() to specify the concave polygon to be tessellated. Unneeded tessellation objects can be destroyed with gluDeleteTess().
I think you can use this to handle polygons with holes as well.
Otherwise you could write the triangulation yourself. But it is not trivial to get a robust and fast implementation working.
Good luck.
But if I understand it correctly you could do this in OpenGL.
This is from www.opengl.org
Polygon Tessellation
The polygon tessellation routines triangulate a concave polygon with one or more contours. To use this GLU feature, first create a tessellation object with gluNewTess(), and define callback routines that will be used to process the triangles generated by the tessellator (with gluTessCallBack()). Then use gluBeginPolygon(), gluTessVertex(), gluNextContour(), and gluEndPolygon() to specify the concave polygon to be tessellated. Unneeded tessellation objects can be destroyed with gluDeleteTess().
I think you can use this to handle polygons with holes as well.
Otherwise you could write the triangulation yourself. But it is not trivial to get a robust and fast implementation working.
Good luck.
Author
Yeah, ernow got it right, I want to cut one or more holes in a concave/convex polygon.
And no, I am not using OpenGL, I am using OpenInventor, though I wouldnt mind do it manually as long as I have the algorithm.
And no, I am not using OpenGL, I am using OpenInventor, though I wouldnt mind do it manually as long as I have the algorithm.
I just did this.
yuck, the outer polygons should be triangles. Perform the decal clipping algorithm for each of these triangles. There will be more subdivisions, but this is only a handful of vertices we're talking about. 40 vertices is nothing once it's been calculated and splatted on the wall... unlike using the stencil buffer which is also quite fast, but requires extra rendering each frame.
I couldn't find any, so I did my own approach. I realized that it's possible to represent the outer triangles (world geometry) as three planes.
pseudo code:
for each triangle point
TrianglePlane = PlaneFromPoints(tripoint, tripoint[(i+1)%3], tripoint + triangle_normal)
Flip the planes if necessary so that they face away from the third point each. The third point of each triangle is tripoint[(i+2)%3]. When I did this, I'm pretty sure that the number of flips was 0 due to the order.
Now if you begin a decal as 4 points, collect all the nearby coplanar triangles. Of these, collect the triangles that surrounds at least one point of the decal (if a decal point is inside each of the three planes of the triangle).
With this 4 point starting decal, do the following for each of these collected world triangles:
find and add the line segment intersections for each decal point within the triangle going towards the next decal point (only the starting ones, not the extras calculated). Discard any starting points outside the triangle, keep the ones inside. Turn all the points into a set of triangles (usually a fan)... this is a convex shape, there are many ways to do this. If you use a linked list, then the points should be in order depending on how you do it =)
Then possible save into one huge decal, but it's not necessary. If there's an easier method then I'm all ears (if it doesn't involve the stencil buffer).
Quote:Original post by lifeless
An "outer polygon" with N-vertices (could be concave)
yuck, the outer polygons should be triangles. Perform the decal clipping algorithm for each of these triangles. There will be more subdivisions, but this is only a handful of vertices we're talking about. 40 vertices is nothing once it's been calculated and splatted on the wall... unlike using the stencil buffer which is also quite fast, but requires extra rendering each frame.
Quote:Original post by lifeless
Now, I need an algorithm that can create a triangle mesh of all the faces that should be on the clipped polygon.
I couldn't find any, so I did my own approach. I realized that it's possible to represent the outer triangles (world geometry) as three planes.
pseudo code:
for each triangle point
TrianglePlane = PlaneFromPoints(tripoint, tripoint[(i+1)%3], tripoint + triangle_normal)
Flip the planes if necessary so that they face away from the third point each. The third point of each triangle is tripoint[(i+2)%3]. When I did this, I'm pretty sure that the number of flips was 0 due to the order.
Now if you begin a decal as 4 points, collect all the nearby coplanar triangles. Of these, collect the triangles that surrounds at least one point of the decal (if a decal point is inside each of the three planes of the triangle).
With this 4 point starting decal, do the following for each of these collected world triangles:
find and add the line segment intersections for each decal point within the triangle going towards the next decal point (only the starting ones, not the extras calculated). Discard any starting points outside the triangle, keep the ones inside. Turn all the points into a set of triangles (usually a fan)... this is a convex shape, there are many ways to do this. If you use a linked list, then the points should be in order depending on how you do it =)
Then possible save into one huge decal, but it's not necessary. If there's an easier method then I'm all ears (if it doesn't involve the stencil buffer).
Author
Alright, i'm not familiar with the decal clipping algorithm, so I will check on that first. Anyway, does this algorithm work for more than one "holes" inside the outer polygon? Because I did create a simple one, but it only works for one "hole". Regardless, thanks for your help, I may come back to you later for advice in implementation.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
