silhouette drawing

a difficult problem
one method similar to what u said would be set linewidth to 3 + draw the wireframe with a slight negative polygon offset , then redraw the model over the top

anothe possibilty is what i do here (orange outlines over some faces)
draw the model blurred in a color + then redraw the model over it
www.zedzeek.com/conquest_SS.jpg

another method which doesnt give a true siloette is do a
dotproduct( campos-vert, -cam forward ) if its > 0.95

Quote:

Original post by zedzeek a difficult problem one method similar to what u said would be set linewidth to 3 + draw the wireframe with a slight negative polygon offset , then redraw the model over the top anothe possibilty is what i do here (orange outlines over some faces) draw the model blurred in a color + then redraw the model over it www.zedzeek.com/conquest_SS.jpg another method which doesnt give a true siloette is do a dotproduct( campos-vert, -cam forward ) if its > 0.95

Understood but still not anything that I'm not already doing. There has to be a way to draw the silhouette without completely drawing all of the polygons.

Anyone?

Which bits are you worried about? The bandwidth of supplying the polygon data twice or the pixel processing waste of overdrawing so much?

You could fix the latter with a shading program that ditches points whose camera normal is more "forward/backward" than "left/right". The result would be that only polgons which are nearly edge on would have their edges rendered.


Not sending polygons could be done in two ways -- one would be to cull by the polygon normal (in the same way that back-facing polygons are culled, you could cull ones which are front facing before sending.)

Another might be to segment your model geometry, and have a "segment normal". So a cylinder might have eight segments for each octant around its edge. And you turn the segments on and off based on how well the segment normal is aligned with the camera X axis. So you'd render between two and four segments, and lose the remainder. The remaining faces have edges which should still get you a silhouette.

What are you trying to do? Are you trying to do Cel-Shading? There are plenty of examples on cel-shading. Try [google]

try this.
And there is some code here.

cel shading uses silhouette outlines, so you can maybe adapt it for your use.
Hope that helps.

Not sure if this is what you were looking for... but I stumbled across this so I figured id post it.

http://www.gamedev.net/columns/hardcore/silhouettes/

Quote:

Original post by _neutrin0_ What are you trying to do? Are you trying to do Cel-Shading? There are plenty of examples on cel-shading. Try [google] try this. And there is some code here. cel shading uses silhouette outlines, so you can maybe adapt it for your use. Hope that helps.

I've done the research and I've used the code from the Nehe link ... that's the problem, not the solution. In that simplistic example they show the thing I'm trying to avoid ... rendering the mesh twice. There HAS to be a better way. I've done the Google research, I've been to Nehe and Paul's Project.

I'm a GLSL guy too so if you know how to do it shaders, let me know.

Quote:

Original post by Katie Which bits are you worried about? The bandwidth of supplying the polygon data twice or the pixel processing waste of overdrawing so much? You could fix the latter with a shading program that ditches points whose camera normal is more "forward/backward" than "left/right". The result would be that only polgons which are nearly edge on would have their edges rendered. Not sending polygons could be done in two ways -- one would be to cull by the polygon normal (in the same way that back-facing polygons are culled, you could cull ones which are front facing before sending.) Another might be to segment your model geometry, and have a "segment normal". So a cylinder might have eight segments for each octant around its edge. And you turn the segments on and off based on how well the segment normal is aligned with the camera X axis. So you'd render between two and four segments, and lose the remainder. The remaining faces have edges which should still get you a silhouette.

Sorry, I'll explain better and leave screenshots ...

here's the code





[Edited by - adawg1414 on January 31, 2007 5:56:43 PM]

bumpy bump

Anyone?

Quote:

cel shading uses silhouette outlines

I think he wants a REAL silhouette without any internal edges lines showing inside the mesh itself (judging by the screenshot). cel shading doesn't really use proper silhouettes, for info on those you might want to search for info on shadow volumes...

To get rid of those internal edge lines, you could render the outline first (back faces only, thick lines) with depth writing disabled (glDepthMask), then draw the normal mesh over it. This might cause problems if you then draw something behind the object (the edge lines would be overwritten) - you could solve this with a third pass where you draw the outlines with depth writing on, but color writing disabled (glColorMask).

Why are you so paranoid about drawing the mesh more than once? It's a hell of a lot easier than calculating which edges are part of the silhouette. On the other hand if you want stencil shadows you would need to do that anyway.

Quote:

Original post by zppz Quote: cel shading uses silhouette outlines I think he wants a REAL silhouette without any internal edges lines showing inside the mesh itself (judging by the screenshot). cel shading doesn't really use proper silhouettes, for info on those you might want to search for info on shadow volumes... To get rid of those internal edge lines, you could render the outline first (back faces only, thick lines) with depth writing disabled (glDepthMask), then draw the normal mesh over it. This might cause problems if you then draw something behind the object (the edge lines would be overwritten) - you could solve this with a third pass where you draw the outlines with depth writing on, but color writing disabled (glColorMask). Why are you so paranoid about drawing the mesh more than once? It's a hell of a lot easier than calculating which edges are part of the silhouette. On the other hand if you want stencil shadows you would need to do that anyway.

Ok, for one cell shading != outlines. Outlines can be put on any kind of rendering technique. I know you didn’t post that zppz but I had to address that from the other ‘poster’.

Now to address the ‘paranoia’ for rendering meshes more than once … I think it’s sad that people are ok with rendering entire meshes more than once considering that in a game you have to worry about your FPS. The game really needs to worry about collision checks, AI calculations, shadow rendering, and polygon rendering. With all of those calculations happening why would you want to add more polygon rendering on top of that? If in my game I want to render multiple characters with outlines and multiple items with outlines that could quickly drop the FPS 10+ each time something enters the view frustum because I’m rendering everything twice.

A great game example of great outlines is the Xbox360 game Crackdown. Does anyone know how they did it?

Ive recently implemented a sobel filter in HLSL which draws outlines on objects as a post-process (image processing). I took it from this site . If you tweek some of the variables you can get a much more subtle effect then the one shown in the screen shot. Also if you are careful with your textures i.e. dont have hard edges, it wont interfere with internal surfaces. Also because its a post process its only fill-rate limited, simply render your scene to a texture and run the effect on a screen aligned quad with your render target as its texture.

btw the texturing on your screen shot looks realy nice.

Quote:

The game really needs to worry about collision checks, AI calculations, shadow rendering, and polygon rendering. With all of those calculations happening why would you want to add more polygon rendering on top of that? If in my game I want to render multiple characters with outlines and multiple items with outlines that could quickly drop the FPS 10+ each time something enters the view frustum because I’m rendering everything twice.

I think the question here is "With all of those calculations happening why would you want to give the CPU more work to do?" I am assuming the rendering will be done in hardware, in which case it is highly unlikely that the framerate will drop by 10fps when another object is drawn. If it does then either your rendering code needs attention, or your objects are way more complex than I am thinking. However I suspect the 10fps figure is something you made up without really trying it out. Rendering things twice or even four times is not uncommon.

As for the Crackdown screenshot, it doesn't seem to use pure silhouettes, but it doesn't show many internal edges lines either... I wonder what it's doing. For example, near the armpit of the tattoo guy, there is an internal edge line, but there are no edge lines on his hand. I would guess they are using a pixel shader, definitely something more complex than what I mentioned yesterday.

Quote:

Original post by zppz I think the question here is "With all of those calculations happening why would you want to give the CPU more work to do?" I am assuming the rendering will be done in hardware, in which case it is highly unlikely that the framerate will drop by 10fps when another object is drawn. If it does then either your rendering code needs attention, or your objects are way more complex than I am thinking. However I suspect the 10fps figure is something you made up without really trying it out. Rendering things twice or even four times is not uncommon. As for the Crackdown screenshot, it doesn't seem to use pure silhouettes, but it doesn't show many internal edges lines either... I wonder what it's doing. For example, near the armpit of the tattoo guy, there is an internal edge line, but there are no edge lines on his hand. I would guess they are using a pixel shader, definitely something more complex than what I mentioned yesterday.

True rendering is done on hardware, calculations on CPU. Iterating meshes more than once ... CPU. Dropping 10+ FPS is a guess but there will definitely be a drop anywhere up to 10 FPS regardless of the rendering code because rendering multiple items more than once per frame is always a performance hit.

Thanks for your suggestions guys, I'm just going to figure it out with a shader and I'll post what I end up doing because this obviously needs addressing.

Quote:

Iterating meshes more than once ... CPU.

I see, in the code you posted this is certainly true. You could use glDrawArrays or glDrawElements to get around that problem.

Quote:

Original post by zppz Quote: Iterating meshes more than once ... CPU. I see, in the code you posted this is certainly true. You could use glDrawArrays or glDrawElements to get around that problem.

zppz is correct. You need to change your rendering code to use VBOs first of all. There are a number of ways to draw outlined edges only, and they are all a tradeoff between doing work on the CPU and doing work on the GPU. At the simplest level there is the already mentioned drawing the model twice, the first time slightly larger and with reverse culling. On the other end there's what I did here which calculates perfect edges on the CPU and then sends those to the GPU. This method could very likely be adapted to run on the GPU instead. But whichever way you look at it, something (CPU or GPU) is going to have to go through all your edges to determine if they are an outline or an inner edge.

I want to reiterate that drawing your mesh one additional time is nothing nowadays. You're likely already drawing it a number of times for lighting, shadowing, multipass shaders etc.

Quote:

Original post by rick_appleton Quote: Original post by zppz Quote: Iterating meshes more than once ... CPU. I see, in the code you posted this is certainly true. You could use glDrawArrays or glDrawElements to get around that problem. zppz is correct. You need to change your rendering code to use VBOs first of all. There are a number of ways to draw outlined edges only, and they are all a tradeoff between doing work on the CPU and doing work on the GPU. At the simplest level there is the already mentioned drawing the model twice, the first time slightly larger and with reverse culling. On the other end there's what I did here which calculates perfect edges on the CPU and then sends those to the GPU. This method could very likely be adapted to run on the GPU instead. But whichever way you look at it, something (CPU or GPU) is going to have to go through all your edges to determine if they are an outline or an inner edge. I want to reiterate that drawing your mesh one additional time is nothing nowadays. You're likely already drawing it a number of times for lighting, shadowing, multipass shaders etc.

Should you really use VBO's to draw an animated character though? That would require changing them every frame which is supported but doesnt seem like the best option in this case.

Also do you have actual code examples for how you are figuring out the perfect edges because I am interested in implementing this as well and couldnt find anything on your website besides the screenshot and the news post.

VBO's with an animated model == NO NO! I'd have to reset the memory in the GPU every frame of animation!

I realize that rendering models more than once might be needed sometimes but in this situation I'm trying to avoid that. Please stop trying to "optimize" my code.

Thanks for all of your suggestions, if someone has code examples, that would be great!

Anybody have any new info for this problem?

Here is a simple edge detection code in GLSL fragment shader using Laplacian algorithm.



I've never used this code myself, but you can see this is probably not a very fast process having to loop on every fragment/pixel.

I know you don't like drawing models twice, but depending on the complexity of the scene, one might not always be better then the other. Also drawing models with glBegin/glEnd is a very slow process, you should try VBO or display list.

FIRST PART OF POST IS ABOUT PERFORMANCE:
________________________________________
About the VBO's requiring you to overwrite GPU memory each frame: As far as I know, you can use static VBO's even for animated characters if you just do your skinning in a vertex shader instead of the CPU. With all of the other things that the CPU does (AI, etc.), GPU skinning is probably a good move. There are actually some pretty good threads on GPU skinning and VBO's here...
The main drawback to it is that if you have multipass algorithms (particularly shadow volumes or shadow maps), the skinning will be done once for each pass. Still, it's probably better than wasting CPU time sending over every single vertex more than once, especially individually, as you are doing right now. Also, judging by your stance on rendering meshes twice, it doesn't sound like multipass algorithms are all that important to you anyway. (And besides, regardless of CPU/GPU skinning, multipass algorithms will still require you to render models more than once - so there's no difference there except for the skinning).

Anyway, I know you told everyone to stop trying to optimize your code, but to be honest, that's *really* what needs to be done, and you really need to think about this. You have already stated that your concern with the "multidraw" algorithm is performance, but if you care in any way about performance, there are much more important areas to focus on. Right now, you're using immediate mode, which is *certainly* going to produce a 10 FPS hit every time a new object comes into view - if you're lucky enough to even have 10 FPS in the first place. I know this isn't what you're wanting to hear, but immediate mode (i.e. glVertex3f(...)) is completely unsuited for a game engine with any reasonable number of polygons (more than a few thousand per frame), since it completely ties up your CPU and keeps it from doing any other work, while your GPU just sits there at only a few percent utilization. The only reason to ever use immediate mode is if your geometry is changing too unpredictably (completely independent of skinning) and you can't use VBO's or vertex arrays (and then, immediate mode should be restricted to only the things that absolutely have to use it).

I just moved a program from immediate mode to VBO's earlier this week, so I can give you some actual hard figures. I'm rendering a single complex object. I'm not positive how many polygons it has, but I'm pretty sure it has over a hundred thousand (possibly lots more), and I know it has at least 55,000 (because just one of the many meshes in it has over 160,000 edges). Anyway, here are some figures (on an Athlon 64 3000+, GeForce 6800GT), using immediate mode vs. VBO's for the OpenGL fixed pipeline (cheap Gouraud shading), my own Gouraud shader (prettier ;)), and my Phong shader. Please note I actually had to disable VSync so I could find out how many fps I'm getting now (which actually caused my FPS to split up into two ranges, approximately corresponding to odd/even frames). The framerates I'm giving you are "typical" ones, since they also spiked to 1050 FPS and even 2800 FPS and had other occasional deviations (I noticed the 2800 FPS moment using my Phong shader, and it immediately followed a dip to 136 FPS...using that shader, I tended to have a bit larger of a variance):
Immediate Mode VBO
OpenGL Fixed Path: 2.4 FPS 455 FPS on odd frames, 975 on even
Gouraud shader: 2.0 FPS 395 FPS on odd frames, 735 on even
Phong shader: 1.7 FPS 350 FPS on odd frames, 580 on even

That's more than a 200x performance increase...I'd qualify that as less of an optimization and more of an overhaul.



NOW, ABOUT RENDERING SILHOUETTES:
___________________________________

Although it really does sound like it's horribly inefficient, rendering your model twice really is more efficient than the alternative.

What's the alternative, you ask? It's basically the silhouette-finding part of the shadow volumes algorithm. You'll need to know about mesh connectivity and polygon adjacency, which means that unless you plan on doing n linear searches every frame (which in total is O(n^2)), you'll have to store your mesh in some kind of data structure that allows you to access this (like the half-edge data structure explained at http://www.flipcode.com/articles/article_halfedge.shtml).

Now, the way to find silhouette edges for cel-shading purposes is the exact same as finding them for shadow volumes, except you use the view vector instead of the light vector for the dot-product check:
Here's a pretty old tutorial on shadow volumes, and it gives some pseudocode for the silhouette check:
http://downloads.gamedev.net/pdf/VolumeShadowsTutorial-2036.pdf

If you don't want to read that, here's the general idea
Loop through all of your polygons on the CPU, and for each one, perform a dot-product with the face normal of the polygon with the view vector. If it's less than 0, this polygon is back-facing. Now, for each edge in the polygon, do the same test for the opposite polygon. If that one is also back-facing, then the edge between them is *not* a silhouette edge. If it is front-facing, however, then you just found a silhouette edge, so add it to a list of lines to render (or just render it straight out).

Note that if you do it this way, you end up doing a dot-product four times per polygon. There are two ways to avoid this. One is slow, and the other requires a flag to be added to each polygon or edge of your mesh:
1.) The slow way is this: For each face, do the dot product. For each edge, do a search in a sorted list (of lines to render) for the opposite edge. If the opposite edge is in the list, remove it and discard the current edge. Otherwise, add the current edge to the list.
2.) A faster way is, every time you do a dot product, flag the result (whether or not the polygon was back-facing) in the data structure of either the polygon or its edges, and also make sure there's an indication that the test was performed this frame (as opposed to last). Then, for each edge, do a simple lookup of its opposite (or the polygon containing its opposite) to find out the results of the test. If it has not yet been done this frame, do it.

So, now that you've found out the silhouette edges, you can render them. However, this uses so much CPU time that it's MUCH, MUCH faster just to render your mesh again, even if this is the only thing your CPU does for the entirety of each frame (exception: if your pixel shaders are atrociously expensive for the mesh, this silhouette-finding could possibly be faster, but the shaders would have to be so ungodly that they're unsuitable for any fast engine anyway).

Is it possible there's a faster solution out there than brute-force double-rendering? Perhaps...I'm thinking that once geometry shaders are available in OpenGL, you could potentially do this: First, you can store mesh topology and geometry data for every polygon in your mesh in two textures. The first texture would have a row for each polygon, each containing a face normal and the index of a half-edge in the next texture. The next texture would have half-edges, each with the index of the next half-edge and the opposite half-edge in the texture, as well as an index to the face it belongs to in the other texture. Then, for each polygon you render, given an index into one of the textures to indicate either which face this is or a half-edge in the face. In your geometry shader, you could then do the back-face/front-face test for neighboring polygons, allowing you to find out if one of the edges is a silhouette edge. Finally, you can then use the geometry shader to draw that edge as an outline. This has the benefit of making the GPU do the work instead of the CPU, and it has another advantage over the shadow volume-ish solution by allowing you to still store the mesh in a VBO or a vertex array and display list without having to send over silhouette data ever frame.

I'm currently exploring a "topology data stored in texture" solution for a completely different shader I'm developing, so I'm not sure what the drawbacks are. As far as general algorithms go, I'm relatively knowledgeable, but in terms of details, I'm still a noob. In short, I'm not sure if it's possible to reliably index a huge texture (with potentially hundreds of thousands of rows and only a few columns)...it depends on whether all texture lookups have to use floating point coordinates or not. (In face, if anyone actually read this whole post and knows, could you please send me a PM to let me know? LOL...)

Anyway, good luck :)