CODEWITHSUNDEEP
algorithmgeometry2d
krb
krb

Reputation: 16315

A working implementation of the Sutherland–Hodgman algorithm in C?

I'm struggling to find a good, working implementation of the Sutherland–Hodgman algorithm for clipping one polygon by the edges of another polygon. The input polygons are always quads that consist of four points.

The best C implementation I could find is this one which seems perfect and incredibly fast, but unfortunately, it crashes on certain inputs and I'm not smart enough to determine what exactly in the algorithm goes wrong (it works with some input values and breaks with others). This is an example of some values for quads that crash it:

vec_t c[] = {{400,400}, {200,200}, {400,200}, {200,400}};
vec_t s[] = {{300,300}, {100,100}, {300,100}, {100,300}};

poly_t clipper = {4, 0, c};
poly_t subject = {4, 0, s};

poly res = poly_clip(&subject, &clipper);

Can anyone suggest the issue with that algorithm or suggest a better implementation of it that could work with the same style of inputs (outline points)? C is preferred but I could work with any implementation as long as all steps are implemented (I will have to rewrite it in C). I need this to perform mathematical clipping of 2D quads when rendering them.

In the above example, the input quads are both rects, but in reality they can be any convex quads. The output could be anything ranging from 3 to 8 points (the above example should emit a 4 point polygon).

Upvotes: 1

Views: 2344

Answers (2)

Wilt
Wilt

Reputation: 44336

Your points have to be in counterclockwise order...

Upvotes: 0

Kyle Glowacki
Kyle Glowacki

Reputation: 56

The clipper points must define a convex polygon. You seem to have your points in such an order that they define a figure 8. Try : vec_t c[] = {{400,400}, {400,200}, {200,200}, {200,400}};

See the description of the algorithm : http://en.wikipedia.org/wiki/Sutherland%E2%80%93Hodgman

Upvotes: 4

Related Questions