Advertisement
  1. Game Development
  2. Programming
Gamedevelopment

Understanding Sutherland-Hodgman Clipping for Physics Engines

by
Difficulty:AdvancedLength:MediumLanguages:

Clipping is the process of determining what region of space is within another region of space. This is especially important in areas of study such as computer graphics and physics simulation. For instance, when rendering a world to the screen it is best to know what will be on the screen before processing any data. This allows lots of extraneous data to be ignored, while only processing and presenting what will be seen by the user.

In physical simulation, rigid bodies are often found to be interpenetrating - that is, two separate objects overlap. This is bad. Interpenetration is something that never happens in the real world, but is a problem that must be dealt with in collision detection. Often times one shape is clipped against another in order to determine what features are actually touching. From here a collision response can be initiated.

Advanced features of game engines can be implemented with some form of clipping; buoyancy simulation, camera view planes; brittle fracturing, contact generation with the Seperating Axis Test; all of these things (and much more) can be achieved with clipping algorithms. In fact, clipping like this was necessary in my previous tutorial on building a rigid body physics engine.


Prerequisites

This article requires some you have a decent understanding of:

  • Basic linear algebra
  • Simple 3D math

The above areas of study can be learned from a wide variety of resources on the internet (such as Wolfire's guide to linear algebra or Khan Academy - and they're not too hard to learn!


Splitting Planes

Many complex clipping routines involve making use of a single type of operation: splitting a shape with a single plane. Splitting a shape by a plane involves taking a shape and cutting into two pieces through a solid plane.

SplittingPlaneClipping

It is important to realize that splitting a shape with a plane is a fundamental tool in this clipping routine.

See Davide Cervone's excellent animations for a clear demonstration of this:

By Davide P. Cervone. Used with permission.
By Davide P. Cervone. Used with permission.

Sutherland Hodgman Clipping

Sutherland Hodgman clipping is my favorite clipping routine, as it works for clipping line loops against planes. With this algorithm, given a list of input vertices and a list of planes, an output of new vertices that exist purely within the set of planes can be computed.

The term plane can be used to refer to both a plane in 3D and 2D. A 2D plane can also be called a line.

We can imagine the list of vertices as a single polygon. We can imagine (for now) the list of planes as a single line. Visualizing this in two dimensions might look like the following picture:

PolygonSplitting

With Sutherland Hodgman clipping, the polygon on the right is the desired shape, while the red polygon on the left is the input shape, and has yet to be clipped. The blue line represents a splitting plane in two dimensions. Any number of splitting planes can be used; in the above example just a single splitting plane is used. If many splitting planes are used, then clipping would occur one plane at time, cutting away more and more of an original shape to output a new one:

PolygonManyClips

Sides of a Plane

For simplicity, let's work in strict two dimensions. When splitting a polygon against a plane it will be important to know which side of the plane any given point is on.

DistanceFromPointToPlane

Above is the most commonly used way to find the distance from a point to a plane. Note that the dot symbol in the above equation represents the dot product.

The distance does not need to be calculated explicitly; the normal vector n does not need to be normalized (that is, it does not need to have a length of exactly one unit). All that needs to be checked is the sign of the distance result d. If n is not normalized then d will be in units of the length of n. If n is normalized, then d will be in units equivalent to world space units. This is important to realize as it allows for the calculation to be done in order to see if d is positive or negative. Positive d denotes that the point p is on the front side of the plane. Negative means it's on the back side.

Now what exactly do we mean by the "front" and "back" sides of a plane? Well it really depends on what you define front and back as. Usually "front" means that it's on the same side of the plane as the normal.

The Algorithm

Lets dive right into the algorithm. Take a quick scan over the pseudocode:

The algorithm takes an input polygon and some clipping planes, and outputs a new polygon. The idea is to clip each line segment of the input polygon against one clipping plane at a time. This image from Wikimedia Commons demonstrates this quite well:

Sutherland-Hodgman clipping algorithm, by Wojciech Mula.
Sutherland-Hodgman clipping algorithm, by Wojciech Mula.

Each clipping operation has only a few different cases in which to output vertices, and can be outlined like so:

The best way to understand this algorithm is to draw a 2D shape on a piece of paper, and draw a straight line through the shape. Then loop along the vertices of the polygon and perform the Sutherland-Hodgman algorithm and draw the results. This will build intuition about how the algorithm is just running along each line sequentially, making sure to keep all vertices behind the plane.

After your own pencil and paper run, try out this great webpage. There's some awesome visuals and a Java applet (at top of page) that lets the user see portions of the algorithm actually run!

Intersection Calculation

Calculating the intersection of a plane given two points is very simple. The idea is to use the distance calculation to find the distance of each point to a plane. Given these distances, an intersection can then be calculated by using linear interpolation.

Tip: Linear interpolation is an extremely useful concept to understand, having prolific application in all graphics software, and in physical simulation software. Linear interpolation can be colloquially referred to as lerp. Anything can be linearly interpolated from a starting position to ending position, as long as the equation of motion is linear.

In general, the formula for linearly interpolating from start to end with intersection alpha is:

Tip: In the above example, alpha is what is called an interpolant. Interpolants are used in the linear interpolation calculations to calculate positions between starting and ending points.

Knowing this, the distances from the plane to each point can be used as values of which to calculate an alpha interpolant. The variables t1 and t2 can represent the distances to the plane of p1 and p2 respectively.

In this respect, the intersection point is simply a Lerp from the starting point to the end point, given an intersection time.

Extending to 3D

This algorithm can easily be extended into three dimensional space and performed there. (This algorithm could be performed in any higher dimension, whatever that means.) However in practical applications, this algorithm is usually never actually performed in 3D. By using clever inverse transformations, the problem of clipping a 3D polyhedron against a plane can (in certain scenarios) be simplified to a 2D polygon to to polygon clipping routine. This allows significant computational optimization.

Similarly, if one were to study the Bullet Physics source code, one would find that clipping is actually done in a single dimensional space, even though full 3D clipping is really being performed. This is due to the ability to calculate a valid interpolant given only a single dimension of the problem space.

For example, if one knows the intersection time of the x values of a simple problem, this intersection time can be used as an interpolant to perform a Lerp upon a three-dimensional point.

Let's examine this in a little more detail. Take a look at the following diagram:

BallIntersectionSutherland

Assume the yellow line is the ground at a y-position of 0. Now assume the starting y-position is at 10, and the ending y-position is at -1. Let's calculate a valid interpolant and intersection position along the y-coordinate:

The above can be read as "90% of the way from 10 to -1", which would be zero. This interpolant can be applied to arbitrary data types, including a two-dimensional vector:

The above code would actually calculate the correct x-coordinate for the time of impact, without even performing operations with the x-coordinate in order to determine the interpolant. This idea of calculating interpolants and applying them to higher dimensions than from which they were calculated is a great way to optimize code.

Numerical Robustness

There are some problems that can persist when running a naive implementation of this clipping routine. Whenever calculating the intersection point numerical error creeps into the calculation. This poses a major problem when splitting a polygon with a plane while generating output on both sides of the plane. In order to generate output for both sides of a splitting plane the original Sutherland-Hodgman algorithm needs to be modified slightly, and this is where issues will arise.

Whenever an intersection point is calculated, numerical error creeps in. This is a problem as the intersection point calculated from point A to point B will be slightly different than the calculation from point B to point A. In order to avoid such issues, the intersection must be calculated in a consistent manner. This avoids a terrible T-Junction issue. It's okay if there's numerical error as long as the error is consistent.

T-Junction issue: A gap between two meshes which causes triangle rasterization to leave a visible gap in-between three triangles. Usually caused by poor handling of machine epsilon during floating point computation. Possible solutions: consistent vertex transformations; vertex welding post processing.

Another problem is when determining if a point is on one side of a plane or another. For a whole slew of reasons, thick plane checks should be made. The idea is treat a plane as a thick plane, rather than one with an infinitesimally small width. This allows for an additional case to arise within the Sutherland-Hodgman routine: the on the plane case.

If any point is found to the on the clipping plane, just push the endpoint. This will bring the 3 case count to 4 in total. For more information about EPSILON, see here.


References and Source Code

The best reference for this clipping algorithm resides in Christer Ericson's Real-Time Collision Detection book (aka the Orange Book). You can find this book in pretty much every game studio in existence.

Beyond shelling out lots of money for a book, there do exist a couple of free resources:


Conclusion

Sutherland-Hodgman clipping is a great way to perform clipping in both 2D and 3D space. This type of routine can be applied to solve many various problems, some problems of which are applicable in rather advanced areas of study. As always please feel free to ask any questions in the comments section below!

Advertisement
Advertisement
Looking for something to help kick start your next project?
Envato Market has a range of items for sale to help get you started.