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