Sign in to follow this  
Jason Z

Fast Silhouettes Article

Recommended Posts

I have posted an article that presents a (as far as I know) novel method for rendering silhouettes. The article is posted in my journal for those of you that are interested in checking it out. You can find it here along with a demo program for it: Journal Entry Hopefully this article will still end up on the main posting, but I don't know if it will or not. Please feel free to provide any feedback that you have, good or bad.

Share this post


Link to post
Share on other sites
I did some stuff on silhouettes a while ago also (image), and I think there's at least one problem with your algorithm: it currently doesn't handle thick borders (as my image does). This is of course due to you working with and extruding edges, whereas the algorithm I devised offsets vertices to the exact corner of two neighbouring silhouette edges.

While I never did implement my algorithm on the GPU, I did find a paper of someone who did. I've just had another search for it, but unfortunately couldn't find it.

I'm not sure of the specifics anymore, but I know it only added an additional vertex for each existing vertex. It then added an additional attribute (a single value) which indicated if the vertex was of the original model (0.f), or of the newly added set (1.f).

Presumeably it created a new set of indices which would create fins along ALL edges. Then in the vertex shader the calculation for silhouette was done, and if it was determined that the edge was NOT a silhouette, the additional vertex was not offset. This created a degenerate triangle/quad, which the hardware should be able to strip away. If the edge WAS on the silhouette, the vertex was extended by a specific amount multiplied by the additional attribute. This caused the original vertices to stay where they were, and the added vertes (with value 1.f) to get the full offset.

The only thing I'm missing here is how the vertex shader was able to calculate if the edge was on a silhouette. But I guess that did work similar to how you are doing it. I'll see if I get a chance to check my backups, I think I might still have the paper somewhere.

Share this post


Link to post
Share on other sites
Hi Rick,

Did you write a paper on your algorithm? It seems like my algorithm could be slightly modified to handle the situations that you mention - simply adding a normal per vertex to the silhouette mesh would be sufficient.

Did you produce a demo of your algorithm in action? If you did write up a paper, I would be very interested in seeing your work and comparing it with mine to see how we handled things differently.

Thanks for the response.

Share this post


Link to post
Share on other sites
No, I didn't write anything up on my algorithm, but I should have a working version somewhere, along with source. I'll have to search my backups for those also.

I'll get back to you.

Share this post


Link to post
Share on other sites
I also have an extremely fast silhouette algorithm of my own, which executes entirely in hardware on a fixed function OpenGL pipeline. The first time I coded it was on a Voodoo 3 back in 2002: http://arctangent.8k.com/oldprj/mod3.jpg This is a very old screenshot, when I get home to my computer I can make and post a higher quality shot using better tweaked code.

The algorithm draws silhouettes around objects by drawing all edges of an object, and letting the Z buffer decide which lines are actually an edge that needs to be drawn:

-Enable glPolygonOffset, so that polygon fills are rendered above lines of the same depth.

-Render all the geometry normally.

-If you are using the depth buffer function GL_LEQUAL, switch to GL_LESS at this time. (GL_LEQUAL could potentially introduce z-fighting with the outline vs. the polygon fills when objects are far away from the camera.)

-Render objects to be outlined, in black unlit wireframe.


This has the following effects:

-Most of the lines drawn will be behind the polygons fills, and will fail the z-test. It is (at least at the time I started doing this) faster to send an edge to the video card than to figure out whether or not it should be drawn.

-Lines at the edges of polygons will not be completely obstructed by polygon fills, and will be visible.

-When rotating a cartoon outline object, traditional algorithms that simply elect to draw or not draw a particular line, result in harsh edges and lines popping on and off. My z-buffer silhouette algorithm does not do this: a single line can be anywhere from not shown to thin, to thick, depending on viewing angle. A line does not simply pop on and off, it begins to appear a few pixels at a time, then as the object continues to rotate, a particular line will gain strength and thickness. Then as a feature on the surface of an object begins to rotate out of view, the line starts to thin out, until it is completely invisible again.

Share this post


Link to post
Share on other sites
Interesting method DracoLacertae. Sounds like it would work well.

It is a bit at odds with what I was trying to do, since I was trying to have lines of the same thickness everywhere :D

Share this post


Link to post
Share on other sites
I've found *some* source although I can't guarentee it's the latest. This zip file contains the source for the app (minus my engine) and an executable. You'll need the glut dll for it apparently (don't remember why).

The source to calculate the silhouettes should be in silhouetteDetection.cpp/.hpp, and it's used in mywindow.cpp in the RenderModel function. Most of the utility stuff should be fairly clear, but feel free to post if you have any questions.

Share this post


Link to post
Share on other sites
Thanks a bunch for the demo - I will have to dig into the code later on tomorrow. Did you ever adapt your method to be able to render ridges and valleys as well? This was one of the main drivers behind my implementation - to be able to render ridges, valley, and silhouettes all at once.

Thanks again for the post, I'll give you some feedback on it as soon as I can.

Share this post


Link to post
Share on other sites
I ran the demo and I noticed that there are some internal lines being marked as edges. Probably if its only for edges though, but seriously, these "lines" are not some of the type of silhouettes that some algorithms actually needed.

For example, there are 2 beams in the demo that forms a corner. Because the algorithm tries to follow the actual silhouette definition, the surfaces between the 2 beams that form the corner will have a line marked. But those surfaces have approximately the same surface normals since I could see that the surfaces try to touch each other.

So far, I am using the per-pixel method but with an Early-Z pass to kill off >98% of the fragments before executing a very expensive silhouette detection filter.

There are 2 other things I tried to look out in your algorithm (which I needed):
a)Are silhouettes marked only on occluding surfaces?
b)Is a there a way to directly compute a silhouette tangent?

Edwin

Share this post


Link to post
Share on other sites
Quote:
Original post by Jason Z
Thanks a bunch for the demo - I will have to dig into the code later on tomorrow. Did you ever adapt your method to be able to render ridges and valleys as well? This was one of the main drivers behind my implementation - to be able to render ridges, valley, and silhouettes all at once.

Thanks again for the post, I'll give you some feedback on it as soon as I can.


No, I never did. I was only trying to get true silhouettes. But I assume ridges an d valleys just have a different cutoff point for not rendering. For those the fixed-width line might become a problem though.

I did another search for the article I mentioned, and it *might* be the article in ShaderX. That article does require more than just a single added vert though, so either I'm mistaken, or it's not the article I was thinking about. They use the 0.f/1.f trick for extruding the fins though.

Share this post


Link to post
Share on other sites
Quote:
Original post by edwinnie
I ran the demo and I noticed that there are some internal lines being marked as edges. Probably if its only for edges though, but seriously, these "lines" are not some of the type of silhouettes that some algorithms actually needed.

For example, there are 2 beams in the demo that forms a corner. Because the algorithm tries to follow the actual silhouette definition, the surfaces between the 2 beams that form the corner will have a line marked. But those surfaces have approximately the same surface normals since I could see that the surfaces try to touch each other.

So far, I am using the per-pixel method but with an Early-Z pass to kill off >98% of the fragments before executing a very expensive silhouette detection filter.

There are 2 other things I tried to look out in your algorithm (which I needed):
a)Are silhouettes marked only on occluding surfaces?
b)Is a there a way to directly compute a silhouette tangent?

Edwin
Is this directed to me or to rick appleton?

Share this post


Link to post
Share on other sites
I am not really clear on what issues you have found - maybe you could post a screenshot with the area highlighted that you think is in error?

Share this post


Link to post
Share on other sites
ok, but first, can u update ur demo to show different colors for silhouettes, ridges, and valleys. I need to be sure that what I saw in error is not a ridge nor valley first.

regards
Edwin

Share this post


Link to post
Share on other sites
Hello Edwin. Replace the 'Edge_Mesh.fx' file in the Data/Effects folder with the following text file:

//-----------------------------------------------------------------------------
// Edge_Mesh.fx
//
//-----------------------------------------------------------------------------

//-----------------------------------------------------------------------------
// Parameters
//-----------------------------------------------------------------------------
float4x4 Transform : WorldViewProjection;
float4x4 ModelWorld : World;
float4 CamPosition : ViewPosition;

float4 scale : ViewParm0 = float4(0.1,0.1,0.1,0.1);
//-----------------------------------------------------------------------------
// Structures
//-----------------------------------------------------------------------------
struct vertex
{
float3 position : POSITION;
float3 normal : NORMAL;
float3 tangent : TANGENT;
float ridge : TEXCOORD0;
};
//-----------------------------------------------------------------------------
struct fragment
{
float4 position : POSITION;
float4 color : COLOR;
};
//-----------------------------------------------------------------------------
struct pixel
{
float4 color : COLOR;
};
//-----------------------------------------------------------------------------

//-----------------------------------------------------------------------------
// Vertex shaders
//-----------------------------------------------------------------------------
fragment VS( vertex IN )
{
fragment OUT;

float4 WorldPos = mul( float4(IN.position, 1), ModelWorld );
float3 P = WorldPos.xyz;

float3 N = mul(IN.normal, (float3x3)ModelWorld); // world space face 1 normal
float3 T = mul(IN.tangent, (float3x3)ModelWorld); // world space face 2 normal
float3 E = P - CamPosition.xyz; // un-normalized world space eye to position

OUT.color = 0;

float EdotN = dot(E,N); // positive for forward facing, negative for back facing
float EdotT = dot(E,T); // positive for forward facing, negative for back facing

//float extend = 0.1 * (length(E) / 75);
float extend = scale.x * (length(E) / 75);

float3 newPos = IN.position + IN.normal * extend;


if ( ( EdotN * EdotT ) < 0 ) // silhouette detection
{
OUT.color.a = 1; // make this visible
OUT.color.rgb = float3( 0, 1, 0 );
if ( EdotN > 0 ) // extend only the front facing vertices
{ // in the opposite direction
newPos = IN.position-IN.normal*extend;
}

}

OUT.color.a += IN.ridge; // set visibility for ridges and valleys (pre-computed)

OUT.position = mul( float4( newPos, 1), Transform ); // output the final vertex position

return OUT;
}
//-----------------------------------------------------------------------------

//-----------------------------------------------------------------------------
// Pixel Shader
//-----------------------------------------------------------------------------
pixel PS( fragment IN )
{
pixel OUT;

OUT.color = IN.color;

return OUT;
}

//-----------------------------------------------------------------------------
// Techniques
//-----------------------------------------------------------------------------

technique EdgeMesh
{
pass P0
{
AlphaTestEnable = true;
AlphaRef = 0x00000001;
AlphaFunc = Greater;

VertexShader = compile vs_1_1 VS();
PixelShader = compile ps_1_1 PS();
}
}
//-----------------------------------------------------------------------------


That essentially just writes a color whenever a silhouette edge is detected. Let me know if you still see a problem... [grin]

Share this post


Link to post
Share on other sites
ok, here's the image with the problem:
Free Image Hosting at www.ImageShack.us

The small red arrows are pointing to the part of the green lines. That part is not a silhouette.

regards
Edwin

Share this post


Link to post
Share on other sites
Yes, I see now. This was actually intended when I created the model. That section is a welded cross section on a machine that I was modelling, and it was desired to have it stand out as a separate piece. This could be eliminated by changing the MS3D file to have those two planes share vertices in that corner.

Sorry - that was my fault for not clearing that up sooner...

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