Sign in to follow this  
STufaro

[Solved] Thick (Constant-Width) Lines Using Quads

Recommended Posts

STufaro    183
Hi all,

I am making a 3D level editor for my game and would like to add grid lines, but ones better (namely, thicker) than the thin 1-px lines created by rendering a LINE_LIST. I've run across several posts using D3DXLine, and tried it myself, but found that the transforms were buggy, so I set out to make 3D lines from quads aligned to face the camera (i.e., billboards). I do not completely understand billboards, but I've been playing with them long enough to have a general feel of how they work and can create some on my own.

I would like to keep the lines a constant thickness, no matter how close or far the camera is from them. I tried using an orthographic projection to no avail, and I've also tried doing a perspective divide manipulation (or rather, multiplication) on my billboard's vertices to find out how much I should scale them. No attempt so far I've made looks even remotely correct, and I think I'm just confusing myself trying to mess with different things for an easy solution...

Can anyone outline the basic steps of how I would go about doing this (e.g., step 1, make quad vertices, step 2, rotate, step 3...etc.)? How would you solve this problem?

An external link of someone solving the same problem, but without perspective (plus I'd rather not use a vertex shader and am having trouble understanding his assembly code):
[url="http://stackoverflow.com/questions/3818287/drawing-lines-in-3d-directx"]http://stackoverflow...s-in-3d-directx[/url]

(Just a note--working in Direct3D9 via SlimDX and C#, so that's why I reference Direct3D-specific names, but I have no need for API-specific examples--anything should work for me.)

Best regards,
-- Steve

-----

[size=5][b]Edit: SOLVED! And I'm very happy...See the following posts...[/b][/size]

Share this post


Link to post
Share on other sites
STufaro    183
Well, after a little bit of struggling yesterday I've come up with a buggy, but somewhat-working, implementation.

My basic steps are as follows:[list=1]
[*][b]Get the vector of the line:[/b]
[CODE]lineDirection = (lineStart - lineEnd)[/CODE]
[*][b]Find our soon-to-be constructed quad's normal as:[/b]
[CODE]quadNormal = cameraPosition - lineMidpoint[/CODE]
Where lineMidpoint = ((lineStart + lineEnd) / 2). I reason this should be the quad's normal since the quad will always be facing the camera, like a billboard.
[*][b]Get the direction along which we should extrude vertices from our line[/b], which is the cross product of lineDirection and quadNormal:
[CODE]extrudeDirection = Vector3.Cross(lineDirection, quadNormal)[/CODE]
Normalize extrudeDirection.
[*][b]Get the W of lineStart and lineEnd by transforming them by the viewMatrix * projectionMatrix.[/b]
[CODE]wStart = (Vector3.Transform(lineStart, viewMatrix * projectionMatrix)).W
wEnd = (Vector3.Transform(lineEnd, viewMatrix * projectionMatrix)).W[/CODE]
[*][b]Extrude vertices from the line along the extrudeDirection vector, in some multiple of the W.[/b]
[CODE]Vector3 startVert1 = lineStart + extrudeDirection * wStart * lineWeight
Vector3 startVert2 = lineStart - extrudeDirection * wStart * lineWeight
Vector3 endVert1 = lineEnd + extrudeDirection * wEnd * lineWeight
Vector3 endVert2 = lineEnd - extrudeDirection * wEnd * lineWeight[/CODE]
[*][b]Connect the vertices to form a quad.[/b]
[/list]
And therein lies the hitch, which took some unraveling for me.

If you are far from the line, both W's will be positive, which is fine, since presumably you connected your four vertices to form a quad with the diagonal of the triangles being shared between them. Un-projected, this quad looks like a trapezoid, with bases on either side, and one base larger than the other to cancel out the W-divide. Everything works well.

However, if you get close to the line and rotate the camera a bit to face one end, one vertex will go off-screen and behind the camera, and thus one of the W's will be negative. This mathematically legit, I've reasoned, but your vertices that you extrude will be created on opposite sides of the line. If you don't change the way your vertices are connected in this situation, your triangle's diagonals will cross, because on one side of the quad the vertices have been flipped over the line. The result is you get an extra "flap" of the triangle either below or above your line, which confused me to no end yesterday. In the below [s](high-quality rendering)[/s] diagram, the red section is what I'm talking about.

[img]http://i44.tinypic.com/b4x24m.png[/img]

To get rid of the red section, I adjusted the vertices of the triangles to the [b]point where the diagonals cross[/b] [b]when one of the W's was negative.[/b] That way, you'd get just the white part of the two triangles. (To get this point, I solve the equations of the two lines in 3D (since they're coplanar, they will intersect).)

That seemed to solve the problem in one little test I did, but when I scaled up and made a bunch of lines for my in-game grid, problems galore popped up, including some of the same problems the D3DXLine class seems to have (it appears to negate the transforms when you get close), which is not a good sign.

If anyone had the patience to read my essay on drawing lines with quads and has an idea on where in this process I went wrong, please do let me know--I'm very curious. I also don't want to abandon thick lines, but for now I'm just using a LINE_LIST to draw my grid.

I'll keep us updated if I come up with anything else, too.

Best,
-- Steve

Share this post


Link to post
Share on other sites
Jason Z    6434
That is a great post - very informative and clearly explaining what you did and what you are seeing. Nice job providing the information for other people to use!

Here is my take on what is going on. The W-value is only negative when it is behind the near clip plane as you mentioned, so your correction should be working if you are solving for the location where the W-values becomes zero. When their W-values are both equal to 0, then you should get no flying vertices, and your extra flap should disappear.

As far as I can tell, solving for the diagonal may help in some/most cases but doesn't seem like the correct place to move them to (at least to my understanding anyways). Try solving for the W=0 point (or perhaps with a small positive offset for good measure) and see if it helps to improve the situation.

Share this post


Link to post
Share on other sites
STufaro    183
Jason,

Thanks for the fast reply and the idea! It turns out that the point where the triangles cross will be the W = 0 point, so your thinking was spot-on and a lot more exact than mine [img]http://public.gamedev.net//public/style_emoticons/default/smile.png[/img] (I was taking potshots in the dark hoping that the point I picked would keep the perspective--I'm glad I now know the reason).

However, your reply inspired me to try something else, and [b]I managed to solve my problem![/b]

I was solving for the point where the triangles crossed by parametrizing the equations of the 3D lines, not realizing that if I had a line in the pure Z direction (which I did since I'm making a grid), I could not always rely on the X and Y vectors of the line to parametrize it, since I would occasionally get a NaN in (I parametrize and solve for the line intersection point as shown in this link: [url="http://mathforum.org/library/drmath/view/63719.html"]http://mathforum.org...view/63719.html[/url])

Therefore, I needed to add a bit to my code:

[CODE]
if ((extrudeScale1 < 0) ^ (extrudeScale2 < 0))
{
// just assume line direction won't be hurt by using X and Y
float x1 = line1start.X;
float x2 = line2start.X;
float y1 = line1start.Y;
float y2 = line2start.Y;
float a1 = line1vec.X;
float a2 = line2vec.X;
float b1 = line1vec.Y;
float b2 = line2vec.Y;

if ((Math.Abs(lineDirection.Y) < 0.001f) && (Math.Abs(lineDirection.X) < 0.001f))
{
// if the line is purely in the Z direction, however, we need to use Z instead of Y
y1 = line1start.Z;
y2 = line2start.Z;
b1 = line1vec.Z;
b2 = line2vec.Z;
}
else if ((Math.Abs(lineDirection.X) < 0.001f) && (Math.Abs(lineDirection.Z) < 0.001f))
{
// and similarly, if purely in the Y direction, we need to use Z instead of X
x1 = line1start.Z;
x2 = line2start.Z;
a1 = line1vec.Z;
a2 = line2vec.Z;
}
float t1 = (y1 - y2 - b2 * ((x1 - x2) / a2)) / (b2 * a1 / a2 - b1);
float x = line1vec.X * t1 + line1start.X;
float y = line1vec.Y * t1 + line1start.Y;
float z = line1vec.Z * t1 + line1start.Z;
}
[/CODE]

Where line1vec and line1start are the starts of the _diagonals_ of the quad, and lineDirection is the direction of the line we are _drawing_. Sorry it's not very clean...and there's probably some optimization to be made too. As usual I don't make any guarantees...[img]http://public.gamedev.net//public/style_emoticons/default/smile.png[/img]

I don't completely understand I had to use Z instead of X when drawing a Y-line (I assume it has to do with the extrusion direction being in the pure X-direction when I was sitting along the Z-axis?), but it did work. Now I have thick lines! (I'm wondering if it was worth the effort and hair-pulling for my little project--but hopefully it will be for someone else).

[img]http://i40.tinypic.com/moo7t.png[/img]

They're not exactly award-winning without a fair amount of AA, and even then they're pretty ugly. There may even still be some artifacts in there...but I think I'm ready to call them good-enough for my game [img]http://public.gamedev.net//public/style_emoticons/default/smile.png[/img]

Thanks again, Jason, for your help--without the help and encouragement of the GD community I'd have made far less progress on my project.

Best regards,
-- Steve

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this