‹

›

X

Mar

21

2015 K.I.S.A Devlog 014: Drawing Curves |

by Oracizan |

It's been a while since I've written a technical devlog about some minutiae of K.I.S.A's code. So here's one about rendering hair by making use of a textured curve. It's presented in a way that's divorced from the specifics of its usage in K.I.S.A, similar to the post about cloth physics, so it should be easily generalizable to other usages.

**THE WHY**

Throughout development, Kisa's hair has gone through many changes. One of the most recent iterations was a cloth mesh.

Hair is not cloth. It is a fine approximation for many circumstances, but the issue I kept running into is that different situations required the hair to behave in different ways. It needed to flow behind her when she ran, hang flat but constrained against her neck when standing, wave wildly above her head as she fell...I found myself coding special exceptions more often than I was relying on the base cloth physics engine, which kind of defeated the purpose of even using the cloth engine.

I decided to simplify. I pared Kisa's hair down from a full cloth mesh to a single chain of points.

Though the chain is less fluid than the cloth mesh, it compensates for this with several advantages: It is computationally cheaper to move and to draw. A hair texture can be applied without fear of unappealing overlap. When resolving special exceptions - of which there are fewer - it's easier to manipulate 6 points and 5 constraints instead of 30 points and 47 constraints.

Kisa's hair is not the 1 pixel wide green line that we see in the above image, however. It has width (52 pixels, in case you were wondering) as well as height, which means that I need to compute the vertices on either side of the line. The final image also needs to correctly represent the curve of the hair when it is not hanging straight, so I can't blindly cast out vertices at right angles from each point.

**90 DEGREE BLIND METHOD**

Blindly casting vertices at right angles from each point is a good starting point, however. Below you'll see each point as a blue numbered circle, and each constraint as a yellow line. The vectors at right angles from the ray between each consecutive point are the aqua and green arrow. The outside vertices of the curve are indicated by the endpoints of the arrows.

The blind casting approach works for the parts of the curve between 0-1-2, because the 3 points are nearly collinear. In effect, you'd be drawing a rotated rectangle.

2-3-4 is where this method falls apart. If we draw each section of the curve as a rectangle, we start to see obvious overlap on the inner edge of the curve, and gaps on the outer edge of the curve. Each section needs to share vertices with each other, not create their own independently. Instead of 4 vertices for every point on the curve, let's try 2.

**BISECTOR METHOD**

To achieve 2 vertices per point, we leave the vertices of the first and last point alone, but 'average' the pair of vertices on the inner edge and outer edge of the curve for each middle point. In practice, this means that we take the bisector of each pair of consecutive rays to find the inner edge of the curve, and then flip it around to find the outer edge of the curve. This method works well, and it is good enough for many applications, in addition to being faster than more complex methods.

Here is a curve calculated with the Bisector Method, drawn using a triangle strip at the resulting vertices. If the curve involves enough points, the result is smooth and visually satisfying. For the purposes of K.I.S.A, however, I am interested in using as few points as possible, and I dislike how sharp the outer edge of the curve is. Farther and deeper we travel, friends.

**HYBRID METHOD**

In order to smooth the outer edge of the curve out, we can use data from the 90 Degree Method and combine it with the Bisector Method. By taking the two 90 degree vectors as well as their bisector, we can add 2 extra vertices to the outer edge of the curve very easily. This looks much nicer than using just a pure bisector method.

In order to utilize this method, we will need to figure out whether the outer edge is currently on the left-hand side or the right-hand side of the curve - outer edge being the side of the curve where gaps instead of overlap form in the 90 Degree Method. This is trivially computed by determining whether the difference in angles of two consecutive rays is positive or negative.

The downside of this method is that we must use a triangle list instead of triangle strip, because there's no clean way (that I can see) to create a continuous strip of triangles while hitting all of the vertices a single time.

The final touch is adding a texture, which is just a matter of calculating the correct UV coordinate for each point.

You'll notice in some of the images that the width of the left-hand side of the curve is smaller than the right-hand side of the curve. This is functionality required to draw Kisa's hair correctly. If we ignore that for now and pretend that the points rest in the exact middle of the curve, then the three V coordinates we need are simple.

If we take into account that the left-hand side of the curve and the right-hand side of the curve can be different widths, then the 0.5 becomes:

That's it. You know everything about how curves are drawn in K.I.S.A.

There are certainly ways to make a curve look better than with the above methods. Feeding the Bisector Method the points of a spline calculated from the provided points would result in a smoother curve, for example. You'll also notice that the outer edge of a curve is invariably longer than the inner edge of the curve, which means we're fudging the U texture coordinate at some points (The U coordinate is repeated for all three vertices on the outer section of the curve associated each point).

For the purposes of K.I.S.A, the above Hybrid Method provides a balance of speed and acceptable visuals. Either a finer gradient of points or pre-calculating the length of each side of the curve would help fix the fudged U coordinates, but I do not require it. I leave this as a task for someone who desires this functionality.

You can download an example GameMaker: Studio project with code from this devlog here.

Throughout development, Kisa's hair has gone through many changes. One of the most recent iterations was a cloth mesh.

Hair is not cloth. It is a fine approximation for many circumstances, but the issue I kept running into is that different situations required the hair to behave in different ways. It needed to flow behind her when she ran, hang flat but constrained against her neck when standing, wave wildly above her head as she fell...I found myself coding special exceptions more often than I was relying on the base cloth physics engine, which kind of defeated the purpose of even using the cloth engine.

I decided to simplify. I pared Kisa's hair down from a full cloth mesh to a single chain of points.

Though the chain is less fluid than the cloth mesh, it compensates for this with several advantages: It is computationally cheaper to move and to draw. A hair texture can be applied without fear of unappealing overlap. When resolving special exceptions - of which there are fewer - it's easier to manipulate 6 points and 5 constraints instead of 30 points and 47 constraints.

Kisa's hair is not the 1 pixel wide green line that we see in the above image, however. It has width (52 pixels, in case you were wondering) as well as height, which means that I need to compute the vertices on either side of the line. The final image also needs to correctly represent the curve of the hair when it is not hanging straight, so I can't blindly cast out vertices at right angles from each point.

Blindly casting vertices at right angles from each point is a good starting point, however. Below you'll see each point as a blue numbered circle, and each constraint as a yellow line. The vectors at right angles from the ray between each consecutive point are the aqua and green arrow. The outside vertices of the curve are indicated by the endpoints of the arrows.

The blind casting approach works for the parts of the curve between 0-1-2, because the 3 points are nearly collinear. In effect, you'd be drawing a rotated rectangle.

2-3-4 is where this method falls apart. If we draw each section of the curve as a rectangle, we start to see obvious overlap on the inner edge of the curve, and gaps on the outer edge of the curve. Each section needs to share vertices with each other, not create their own independently. Instead of 4 vertices for every point on the curve, let's try 2.

To achieve 2 vertices per point, we leave the vertices of the first and last point alone, but 'average' the pair of vertices on the inner edge and outer edge of the curve for each middle point. In practice, this means that we take the bisector of each pair of consecutive rays to find the inner edge of the curve, and then flip it around to find the outer edge of the curve. This method works well, and it is good enough for many applications, in addition to being faster than more complex methods.

Here is a curve calculated with the Bisector Method, drawn using a triangle strip at the resulting vertices. If the curve involves enough points, the result is smooth and visually satisfying. For the purposes of K.I.S.A, however, I am interested in using as few points as possible, and I dislike how sharp the outer edge of the curve is. Farther and deeper we travel, friends.

In order to smooth the outer edge of the curve out, we can use data from the 90 Degree Method and combine it with the Bisector Method. By taking the two 90 degree vectors as well as their bisector, we can add 2 extra vertices to the outer edge of the curve very easily. This looks much nicer than using just a pure bisector method.

In order to utilize this method, we will need to figure out whether the outer edge is currently on the left-hand side or the right-hand side of the curve - outer edge being the side of the curve where gaps instead of overlap form in the 90 Degree Method. This is trivially computed by determining whether the difference in angles of two consecutive rays is positive or negative.

The downside of this method is that we must use a triangle list instead of triangle strip, because there's no clean way (that I can see) to create a continuous strip of triangles while hitting all of the vertices a single time.

The final touch is adding a texture, which is just a matter of calculating the correct UV coordinate for each point.

C = Current point

T = Total number of points

U = C / (T-1)

T = Total number of points

U = C / (T-1)

You'll notice in some of the images that the width of the left-hand side of the curve is smaller than the right-hand side of the curve. This is functionality required to draw Kisa's hair correctly. If we ignore that for now and pretend that the points rest in the exact middle of the curve, then the three V coordinates we need are simple.

V = 0 **OR** 0.5 **OR** 1

If we take into account that the left-hand side of the curve and the right-hand side of the curve can be different widths, then the 0.5 becomes:

L = Width of the left-hand side

R = Width of the right-hand side

V = L/(L+R)

R = Width of the right-hand side

V = L/(L+R)

That's it. You know everything about how curves are drawn in K.I.S.A.

There are certainly ways to make a curve look better than with the above methods. Feeding the Bisector Method the points of a spline calculated from the provided points would result in a smoother curve, for example. You'll also notice that the outer edge of a curve is invariably longer than the inner edge of the curve, which means we're fudging the U texture coordinate at some points (The U coordinate is repeated for all three vertices on the outer section of the curve associated each point).

For the purposes of K.I.S.A, the above Hybrid Method provides a balance of speed and acceptable visuals. Either a finer gradient of points or pre-calculating the length of each side of the curve would help fix the fudged U coordinates, but I do not require it. I leave this as a task for someone who desires this functionality.

You can download an example GameMaker: Studio project with code from this devlog here.

K.I.S.A

Download

A fairytale about knights and kings, witches and princesses, and a girl who hears a disembodied voice in her head.

Download

A fairytale about knights and kings, witches and princesses, and a girl who hears a disembodied voice in her head.

Vital Spark

Play Online

Humanity has been wiped out by hostile AI. Discover why in this short puzzle platformer.

Play Online

Humanity has been wiped out by hostile AI. Discover why in this short puzzle platformer.

Privacy Policy | Terms of Service | © 2016 by Mutant Dream LLC. All right reserved.