Jump to content

  • Log In with Google      Sign In   
  • Create Account

slayemin's Journal



Thick line rendering revisited.

Posted by , 25 April 2014 - - - - - - · 1,027 views

I realized that the thick line rendering I came up with in my previous post was deeply flawed. I had been drawing thick lines in 3D space but thinking in 2D. I had assumed that the normals for the thick lines would all be the same. Boy, was I wrong!

So, what I'm aiming to do is allow users (myself) to create thick lines in 3D space. To do that, they need to give me a vertex position, an orientation normal, and a line thickness. I need at least two vertices to draw a line.

Anyways, here is the bare bones "user code" to create a series of 5 lines down the X-axis, twisting 90 degrees on each subsequent segment:
lc.AddThickVertex(new Vector3(0, 0, 0), Vector3.Backward, 0.5f);
lc.AddThickVertex(new Vector3(1, 0, 0), Vector3.Backward, 0.5f);
lc.AddThickVertex(new Vector3(2, 0, 0), Vector3.Up, 0.5f);
lc.AddThickVertex(new Vector3(3, 0, 0), Vector3.Forward, 0.5f);
lc.AddThickVertex(new Vector3(4, 0, 0), Vector3.Down, 0.5f);
lc.AddThickVertex(new Vector3(5, 0, 0), Vector3.Backward, 0.5f);
The result is a twisting thick line which looks like a twizzlers licorice stick:
Attached Image

In some cases, the end point of the last line segment may match the starting point of the first vertex. If this happens, I want my thick line segments to loop smoothly and seamlessly.
lc.AddThickVertex(new Vector3(0, 0, 0), Vector3.Backward, 0.5f);
lc.AddThickVertex(new Vector3(1, 0, 0), Vector3.Backward, 0.5f);
lc.AddThickVertex(new Vector3(1, 1, 0), Vector3.Backward, 0.5f);
lc.AddThickVertex(new Vector3(0, 1, 0), Vector3.Backward, 0.5f);
lc.AddThickVertex(new Vector3(0, 0, 0), Vector3.Backward, 0.5f);
Attached Image

I did find the 2D thick line drawing code I was thinking about earlier (codeplex). However, like I realized earlier, it's only for 2D. The mathematics for 2D thick lines is pretty easy and straight forward because you don't have to worry about the thick line normal facing direction. You already know that the normal will always be (0,0,1) so you can make some implicit assumptions with your math. However, what do you do when you get something like this in 3D space?
lc.AddThickVertex(new Vector3(0, 0, 0), Vector3.Up, 0.5f);
lc.AddThickVertex(new Vector3(1, 0, 0), Vector3.Up, 0.5f);
lc.AddThickVertex(new Vector3(1, 1, 0), Vector3.Left, 0.5f);
lc.AddThickVertex(new Vector3(0, 1, 0), Vector3.Down, 0.5f);
lc.AddThickVertex(new Vector3(0, 0, 0), Vector3.Right, 0.5f);
This should create four lines which all face inwards towards the center of the square, like so:
Attached Image

If you're interested in the code and mathematics behind this, here is the function which does it:
/// <summary>
/// Creates the appropriate vertex and index buffers for hard corners for a list of thick line segments.
/// This thick line uses two primitives per line segment, so is best for thick lines with little variation between
/// normals.
/// </summary>
/// <remarks>Pre-conditions: m_tlList should have at least one line segment</remarks>
private void BuildHardCorners(out List<LineVertex> verts, out List<int> indices)
{
	int sizeGuess = 0;
	foreach (KeyValuePair<int, List<ThickLineSegment>> kvp in m_tlList) sizeGuess += kvp.Value.Count;
	verts = new List<LineVertex>(sizeGuess * 4);
	indices = new List<int>(sizeGuess * 12);
	LineVertex[] lastVert = new LineVertex[3];

	/*Note: We already know that the thick line list contains at least one line segment. The calling function takes care of that check.*/

	foreach (KeyValuePair<int, List<ThickLineSegment>> kvp in m_tlList)
	{
		List<ThickLineSegment> SegmentList = kvp.Value;

		lastVert[0] = SegmentList[0].TopLeft;
		lastVert[1] = SegmentList[0].Start;
		lastVert[2] = SegmentList[0].BottomLeft;

		bool loop = false;
		/* Goal: Try to derive the purple lines for every vertex segment. If we can do this, we 
		 * just have to "connect the dots" to draw our line segment lists.*/
		for (int a = 0; a < SegmentList.Count; a++)
		{
			ThickLineSegment curSegment = kvp.Value[a];

			if (SegmentList.Count == 1)
			{
				//there's only one segment in the list, so this is super easy!
				verts.Add(curSegment.TopLeft);
				verts.Add(curSegment.TopRight);
				verts.Add(curSegment.BottomLeft);
				verts.Add(curSegment.BottomRight);
			}
			else
			{

				//we know there there are at least two segments in the list, so we have at least one corner
				//which we need to derive. We don't know how many segments we actually have, so we can't hard code in
				//a solution. We have to generalize it.
				//so, what do we have to do? We have a current line segment and possibly a next and previous line segment.
				//each line segment comes with the four vertex corners already defined (red lines).
				//we have to find the red lines for the adjacent line segments (blue lines).
				//from the red and blue lines, we can sum them together to get the purple lines, which becomes the shared vertex
				float height = (curSegment.Thickness / 2.0f);

				ThickLineSegment nextSegment = null;

				//GOAL: Create a list of vertices required to draw the thick lines
				if (SegmentList.Count >= a + 2)  //do we have a next segment?
				{
					nextSegment = SegmentList[a + 1];
				}
				else if(SegmentList[SegmentList.Count - 1].End.Position == SegmentList[0].Start.Position)
				{
					//we're at the end of the segment list, so let's check for looping
					nextSegment = SegmentList[0];
					loop = true;
				}

				/* Possibilities:
				 * 1. Next = null;
				 * 2. Next = value;
				 * GOAL: Find the shared vertex points between two line segments
				 */
				if (nextSegment != null)
				{

					//the math is somewhat straight forward here: To derive the purple lines, we just sum the verts from the current vertex and the next vertex.
					//then we normalize it to get a directional unit vector, scale it by the height, then translate it to where it should be.
					Vector3 redLine = curSegment.TopRight.Position - curSegment.End.Position;
					Vector3 blueLine = (Vector3.Dot(curSegment.Normal, nextSegment.Normal) >= 0) ? 
						nextSegment.TopLeft.Position - nextSegment.Start.Position : 
						nextSegment.BottomLeft.Position - nextSegment.Start.Position;

					Vector3 purpleLine = redLine + blueLine;
					purpleLine.Normalize();


					Angle t = Angle.FindAngleBetween(-purpleLine, -redLine);
					float length = (float)(height * System.Math.Tan(t.Radian));
					float hyp = (float)System.Math.Sqrt(length * length + height * height);
					purpleLine *= hyp;

					//create the adjusted left side
					LineVertex TopLeft = new LineVertex(lastVert[0].Position, curSegment.TopLeft);
					LineVertex BottomLeft = new LineVertex(lastVert[2].Position, curSegment.BottomLeft);

					LineVertex TopRight = new LineVertex(curSegment.End.Position + purpleLine, curSegment.TopRight);
					LineVertex BottomRight = new LineVertex(curSegment.End.Position - purpleLine, curSegment.BottomRight);

					verts.Add(TopLeft);
					verts.Add(TopRight);
					verts.Add(BottomLeft);
					verts.Add(BottomRight);

					lastVert[0] = TopRight;
					lastVert[1] = curSegment.End;
					lastVert[2] = BottomRight;

					if (loop)
					{
						//adjust the left verticies of the first line segment to match the verts of the last line segment
						LineVertex top = verts[0];
						LineVertex bottom = verts[2];
						top.Position = lastVert[0].Position;
						bottom.Position = lastVert[2].Position;
						verts[0] = top;
						verts[2] = bottom;
					}
				}
				else
				{
					//We're creating the last segment and its not looped.
					//we have to check the normals between this segment and the previous segment
					float normalDot = Vector3.Dot(curSegment.Normal, SegmentList[a - 1].Normal);
					
					LineVertex TopLeft = new LineVertex(lastVert[0].Position, curSegment.TopLeft);
					LineVertex TopRight = (normalDot >= 0) ? curSegment.TopRight : curSegment.BottomRight;
					LineVertex BottomLeft = new LineVertex(lastVert[2].Position, curSegment.BottomLeft);
					LineVertex BottomRight = (normalDot >= 0) ? curSegment.BottomRight : curSegment.TopRight;

					if (normalDot >= 0)
					{   //Since we're swapping the top and bottom verts of the right side, we also gotta swap the UV coordinates
						Vector2 tmpUV = TopRight.UV;
						TopRight.UV = BottomRight.UV;
						BottomRight.UV = tmpUV;
					}

					verts.Add(TopLeft);
					verts.Add(TopRight);
					verts.Add(BottomLeft);
					verts.Add(BottomRight);
				}
			}
		}

		//We've now got a list of all of the vertices, in order. Now, we have to create the index buffer.
		//note that we're going to do both sides.
		for (int segmentID = 0; segmentID < SegmentList.Count + 1; segmentID++)
		{
			//clockwise
			indices.Add(segmentID * 4 + 0);
			indices.Add(segmentID * 4 + 1);
			indices.Add(segmentID * 4 + 2);

			indices.Add(segmentID * 4 + 3);
			indices.Add(segmentID * 4 + 2);
			indices.Add(segmentID * 4 + 1);

			//counter-clockwise
			indices.Add(segmentID * 4 + 2);
			indices.Add(segmentID * 4 + 1);
			indices.Add(segmentID * 4 + 0);

			indices.Add(segmentID * 4 + 1);
			indices.Add(segmentID * 4 + 2);
			indices.Add(segmentID * 4 + 3);
		}
	}
}
I struggled over this far longer than I should have, but I'm pretty happy with the result now.

Next up... revisiting the thick lines with rounded corners. I'm honestly not looking forward to it since I anticipate it'll be a lot harder, but once that's done, my line drawing primitive system will finally be complete and ready for use. Whew! This is a lot harder than I thought it would be. Why did I choose to solo a 3D game in XNA, starting from scratch?!


Lines with rounded corners

Posted by , 17 April 2014 - - - - - - · 842 views

My girlfriend asked me today if I'm behind schedule on my game. I didn't really want to answer her, but she pointed out that I was planning on hiring an artist to work with me in December. It's long past December and I'm not really ready for an artist to come in and start making art assets. That's a few months off, at the very least. So, yes, I'm behind by quite a bit from where I expected to be at this point. Why? Because of three primary factors:
  • I don't put in enough hours (~30-40/week)
  • I am building my own game engine (dumb, yes, but it's something I'm enjoying a lot! I've never done it before.)
  • I'm a perfectionist, so I take my time to make sure everything is just right (it works, is well tested, and very robust). I don't want to come back months down the road to refactor something I've forgotten everything about.
Since money isn't really an issue and I have all the time in the world, I'm okay with being behind schedule. It's a rare luxury I suppose...

I'm currently working on building a robust primitive system which is engineered for maximum usability and performance. I'm making slow but steady progress on that.

A few weeks ago, I completed my quads, point sprites, and billboards. Since I'm taking advantage of hardware instancing, I can have thousands of textured quads on the screen and run at 900+ fps (on my crappy dual core dev box).

After finishing the textured quads, next on the list was creating line lists, line strips, thick textured lines, and thick textured rounded lines. I think the thick textured rounded lines was one of the hardest ones to implement because of the math involved (or that I'm just dumb). Long ago, I had seen someone else do the same thing and posting the code to it. I didn't bother to look for it, and I thought I could do a much better job, so I started writing my own.

After much sweat and effort, here's what I came up with!
Attached Image

The white lines are added to show the vertices for the thick line. I also decided to show the underlying triangle structure.
Here are a few tips for anyone else trying to do the same thing:
-Avoid using triangle strips: I tried this at first, reasoning that I could save a teensy tiny bit of memory. In truth, creating triangle fans using triangle strips will cost you extra memory because you have to use ghost vertices. Instead, use triangle lists with index buffers. I think this may even save a smidge more memory, but it's kind of irrelevant. The real savings comes in the code simplicity and maintaining programmer sanity.
-Plan, then code: I'm kind of dumb. I usually can't just start writing code for something complicated and have it work the first time (though, it does happen on occasion). I have to literally draw out pictures and diagrams of what I'm trying to build. Then, I ask myself how I'm going to find the values in my pictures. I might even figure out what the values should be before writing any code. After I have a good plan, I write code to implement it. I constantly check to make sure that my code is doing what I've planned it to do and that the values I get match what I calculated. When I'm done, I run my implementation and see if it works as planned. In some cases, my conceptual planning was wrong or missing something and I have to revise it. When it's all done, what do you do with your notes? Save them! If you need to refactor later, you've got all your working notes, models, and comments to reference.
-Get it working first, then generalize: I sometimes jump right in and start trying to write a generalized solution and end up getting seriously bogged down in the details and quite confused. Sometimes, I scratch my head for hours trying to figure out how to even do a generalized solution to the problem. It's not always possible to immediately see all the patterns and write a generalization for them. So, start from the ground and build your way up, brick by brick. Start with a super simple task and build on it. Hard code your values in first, when it works as planned, then you can generalize.
-Don't trust something works correctly until it's been rigorously tested. This fact alone probably kicks my ass the most. Got a complicated function? Test it by throwing everything you can at it and see if any combo of parameters gives you unexpected results. Example: I wrote a function which tells me how many degrees are between two angles. The angle is always calculated by winding counter-clockwise from the first angle to the second angle. Now, what happens if the first angle is 315 degrees and the second angle is 45 degrees? If the math/logic is too simplistic, it wouldn't be able to handle an unusual case. It may look like it works for every test, but when another function depends on it to work correctly and it doesn't... you're gonna have a bad time. That leads to my next point...
-Don't try to compact your code: You think you can write a function using one or two lines of clever code? Good for you! But don't do it. It's a lot more difficult to debug when you have to squint at a line of code which does five different things at once. Unpack all that code. It doesn't save enough memory and clock cycles to justify wasting extra programmer time unpacking it if there are errors in there. Keep it simple.

Anyways, looking ahead to next week, I think I'll be able to finally tackle my outdated particle system and get that working to perfection with all the primitives I have.





April 2014 »

S M T W T F S
  12345
6789101112
13141516171819
20212223242526
27282930   

Recent Comments



PARTNERS