Continuous Lines in C#
On a previous project I was tasked with creating dynamic lightning that could strike the player if too close to a storm cloud. This was an interesting challenge for me as the lightning had to look great and be dynamically rendered on everything from a high end iOS device to a low end Android device. As this was in the Unity Game Engine the language of choice was C#, which is good as C# is my language of choice these days.
While researching procedural generation for this effect I ran across a lot of implementations that stuck to using multiple line segment structs shoved into a list. This really would not do. A single lightening effect could sprawl out to hundreds or thousands of line segments. Then it would need to be converted into a bill-boarded mesh. The game could have up to 4 Lightning clouds on screen at a time with up to 4 more Queued up above. So at most it would have to support 6 dynamically generated lightening strikes at a time. The lightening had between one and three main bolts, with a probability that at any point along the line another branch could form. It was a big branching fun looking lightening and enough Vector math to crush the heart of the poor mobile cpu.
To work though the why of why not line of segment structures follow with me on a little napkin math. A continuous Line Consisting of 100 segments needs 101 Points. The same 100 segments using a collection of line segments would be 200 Points(Note, as structures, not objects). With six possible lightening effects at once that would bring it to 606 points vs 1200 points. And every point would have to have all sorts of vector math applied to control the angle and distance of a new point, probabilities of branching, only to then be converted into a mesh for rendering. With a single Continuous line much less cpu time and memory gets consumed. A lot of the math is easier, and mesh generation speed is greatly improved.
Of all of the work and testing, and optimizations that went into creating a good looking dynamic lightening effect I am, oddly, most fond of that Continuous Line Class. Not because it is some great programming challenge or neat little hack. But because it was simple and reusable. For all that is said about encapsulation and reuse in OOP programming, the reality, at least for real time applications, is that fast comes first (for example, Open GL is just a big state machine).
As I have future personal projects that will require things to be done to lines I created a new Continuous Line class that is flexible and useful. But a tad more complex as it has more features. It is in the Lines namespace in the project. In the future I will be adding in classes for Line Segments, Lines (infinite length lines), rays, and more complex line representations like Bezier curves to round out the namespace. Below are a list of public and static methods for the class.
The Point Class consists of Vector3: Position, Vector3: Normal, Vector4: Color, float: width.
- Length: Get the linear length of the line
- Merge Lines(a,b): Merge together two lines in order of a,b.
- Split Line(line, index): returns an array of two new lines created from the split point index provided.
- Calculate Point to Point Deltas(Line, delta Type): Returns a new line that represents the delta values from one point to the next. Delta Type dictates if the delta should be calculated as the absolute difference, or the relative difference.
- Add Point(Point): Adds a new Point to the end of the Line.
- Remove Point(index): Removes the Point at the provided index.
- Insert Point(index, Point): Inserts a new point into the line at the provided index.
- Set Point(index, position, normal, color, width): Alter the values of the point at the index provided.
- Get Point(index): Returns the point at the provided index.
- Get Position(index): Returns the Vector3 Position of the point at the provided index.
- Get Normal(index): Returns the Vector3 Normal of the point at the provided index.
- Get Color(index): Returns the Vector4 color of the point at the provided index.
- Get Width(index): Returns the float width of the point at the provided index.
- Get Direction(index): Returns a Normalized Vector3 direction between point at provided index and the next point.
- Length To Point(index): Calculates the length of the line up to the point at the provided index.
- Smooth Points Using Average: Smooths out the line by averaging neighboring points. In the Future there will be smoothing methods for Gaussian and user supplied kernels as well.
- Subdivide Line: Subdivides the line then smooths out the old points. Like subdividing a mesh.
- Append Line(line): Append a new line onto the end of the line.
- Prepend Line(line): Prepend a new line to the beginning of the line.
- Redistribute Points: Slides all of the points in the line so that each line segment is of equal length.
- Resample Line(samples): Resample the line into a new line with the number of points being that of the provided samples.
- Sample Point(position): Samples the line between two points. Given normalize line length.
- Get Segment Midpoint(index A, index B): Returns a new Point from a sample midway through a line segment.
- Sample Segment Point(index A, index B, float T): returns a new Point that is Samples at T between a and b. T is Clamped 0…1.
- Calculate Normals: Calculate the Lines Normals based on its positions.
- Invert Normals: Inverts all of the Normal vectors in the Line.
- Normalize: Normalizes every normal in the line.
- Scale(Vector3): Scales each point by the X, Y, and Z axis provided.
- Uniform Scale(scale): Scales each Point by a single value.
- Insert Point In Line(position): Samples a position on the line (0…1 clamped) and inserts a new Point.
- Does Self Intersect: Returns true if the line intersects itself at any point.
- Get Self Intersection Points: Returns a List of points where the Line intersects itself.
- Get Self Intersections: Returns a List of Intersection Information objects. Intersection Information Objects contain references to the intersecting lines, segments start indexes, and sample distances at the point of intersection for the lines.
- Get Line Intersection Points(Line): Returns a List of Points where two different Line Intersect.
- Get Line Intersections(Line): Returns a List of Intersection Information Objects for each intersection between the two lines.
As you can see from the Methods implemented so far it is a very flexible class that can be used to represent, manipulate, and analyze anything that can be represented as a Continuous Line. It could be used for Lightening, L-Trees, Even KPI over time if you wish. Many more methods are implemented that are not listed as they are more utility methods. For example, Sample Color(position).
The Source code can be found on Bitbucket. If you wish to contribute feel free to branch and drop me a line. It is MIT Licensed so that you can use it for any purpose.