Jump to content
  • Advertisement
Sign in to follow this  
lifeless

Polygon Clipping

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

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?

Share this post


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

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
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.


Share this post


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

Share this post


Link to post
Share on other sites
I just did this.

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).

Share this post


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

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!