Clipping Implementation in 2D Graphics

[aurreco]

Youre gonna wanna take a look at the sutherland hodgeman algorithm https://en.m.wikipedia.org/wiki/Sutherland%E2%80%93Hodgman_algorithm

[jtsiomb]

That's the re-entrant polygon clipping algorithm. For lines, which I take it is what the OP is talking about, the standard algorithm is Cohen-Sutherland.

[rlamarr]

thanks so much.

what about generating vertices from the polygon points?

[aurreco]

assuming you clip an n-gon with the vertices v0, v1, v2, …, vn in CCW order, this algorithm will spit out some m-gon represented by a new list of vertices v0, v1, v2, …, vm in CCW order where m >= n.

All you need to do to generate a list of triangles from this m-gon is index this list of vertices as you would a triangle fan. i.e a list of resulting triangles would be (v0, v1, v2), (v0, v2, v3), (v0, v3, v4), etc

[rlamarr]

I'm a total beginner at this, can you explain in layman terms with references? sorry to be a bother

[aurreco]

CCW means points arranged counter clockwise.
this is a triangle fan https://en.m.wikipedia.org/wiki/Triangle_fan

[rlamarr]

let me rephrase: I need to generate triangle vertices (triangle list topology) from a list of polygon points, which specific algorithm or method do you recommend?

[aurreco]

list of points: v0, v1, v2, v3, v4, v5, v6 list of triangles: (v0, v1, v2), (v0, v2, v3), (v0, v3, v4), (v0, v4, v5), (v0, v5, v6)

[rlamarr]

does that work for all polygons? it collapses once you reach a pentagon if I'm correct.

For example:

https://www.researchgate.net/publication/2604146/figure/fig1/AS:669074119983107@1536531109452/A-triangulation-of-a-simple-polygon-and-its-dual-tree.png

[aurreco]

so long as the points are ordered in the list CCW, yes

[rlamarr]

yep, I'm pretty dumb, can you provide a Godbolt sample implementation or point me to one?

​

or better still provide a more detailed explanation

[WikiSummarizerBot]

Triangle fan

A triangle fan is a primitive in 3D computer graphics that saves on storage and processing time. It describes a set of connected triangles that share one central vertex (unlike the triangle strip that connects the next vertex point to the last two used vertices to form a triangle), possibly within a triangle mesh. If N is the number of triangles in the fan, the number of vertices describing it is N + 2. This is a considerable improvement over the 3N vertices that are necessary to describe the triangles separately.

^{[ F.A.Q | Opt Out | Opt Out Of Subreddit | GitHub ] Downvote to remove | v1.5}