Advertisement Jump to content


This topic is now archived and is closed to further replies.


A polygon cutting algorithm

This topic is 5484 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 have a problem to solve, let me describe it briefly i start with a big polygon with any number of vertices, and a set of other polygons to be cut from it, mush like a wall, then polygons represeting windows, holes, doors in this wall i need to be able to render the big polygon while cutting the places of the holes, i use OPENGL, and all the vertices are coplanar, i need to make the wal become a set of many triangles or polygons, so i can render it while making the holes show whats behing them, any can tell me a good algorithm/procedure to follow? Flutey Shady El Mously Egyptian Game Programmer (there is no knowledge that is not power)

Share this post

Link to post
Share on other sites
One solution could be to render the holes in a texture and to use this texture as a transparent map (I dont know much in multitexturing, but I''m sure this can be done).

But I think this is not what you''re expecting, so what I think you could do :
- be sure you''ve the basic triangle/triangle intersection and substraction : a triangle minus another triangle should give you many sub-triangles (up to 6 I think)
- describe the wall as a set of triangle, all your holes also as triangle sets
- for each hole''s triangle check the wall''s triangles intersections.

Hope this will help

Share this post

Link to post
Share on other sites
Whichever algorithm you go with, you''ll probably need to precalculate this - I doubt you''ll find something which lets you cut the polygon in realtime. Oh, unless you want to use the stencil buffer - you render your holes into the stencil buffer, and then render the big polygon, using the stencil buffer to mask out the holes.

The alternative, as you said, is to split the wall up into many polygons. I don''t know of any official algorithm, but if I were creating one:

For each polygon you want to cut away, take each side of it and slice the big polygon (or all the smaller polygons that this anti-polygon overlaps) along that line. If you''re cutting out a triangle you''ll make 3 cuts, a quad you''ll cut 4, and so on. When you''re done, you''ll be left with a whole load of little pieces. So then you go through and look for adjacent pieces which would form a convex polygon if combined, and combine them.

As I say, I have no idea if that''s the recommended way of doing things. It''s just how I''d try doing it if I couldn''t look it up.

Richard "Superpig" Fine
- saving pigs from untimely fates, and when he''s not doing that, runs The Binary Refinery.
Enginuity1 | Enginuity2 | Enginuity3 | Enginuity4 | Enginuity5
ry. .ibu cy. .y''ybu. .abu ry. dy. "sy. .ubu py. .ebu ry. py. .ibu gy." fy. .ibu ny. .ebu
"Don''t document your code; code your documentation." -me
"I''m not a complete idiot; parts of me are missing." -}}i{{

Share this post

Link to post
Share on other sites

  • Advertisement

Important Information

By using, you agree to our community Guidelines, Terms of Use, and Privacy Policy. 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!