A polygon cutting algorithm
Author
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)
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
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
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{{
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{{
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
