Convex Hulls and Basic Water Simulation

WIP

Water may be implemented in a variety of ways in a game, depending on what is needed. In this work-in-progress article, water will be implemented into a unity game by way of convex hulls, and the Graham’s Scan algorithm.

Convex Hulls?

Imagine you have a set of nails hammered into a wooden board. Taking a rubber band and stretching it around all of the nails will create an outline of a convex polygon (no outside angle is less than 180 degrees). The points on the rubber band comprise the “Convex Hull” of the nails.

One may think of water as a large pool of points, repelling and attracting one another. By computing a convex hull of these points, we may draw a sloshing pool of water by creating a mesh from the hull.

Graham’s Scan Algorithm

Graham's Scan Demo

  1. Select bottom-most point (p0) in the set
    1. Note: In case of a tie, use the leftmost point.
  2. Using polar coordinates, sweep from p0 around the circle to obtain an ordering of points (p1…pn-1)
    1. Note: Polar Coordinates are used for convenience– they make it easier to reason about angles and “orbits”.
    2. Note: If there are ties, remove all but the furthest point from p0.