Cel-shading - Best Method For Outlines?

Okay, so I'm really new to cel-shading and I'd like some opinions.

I pretty much understand the 'inverted mesh' technique that people seem to have been using in blitz. It's neat and simple, but isn't there a danger of running up huge triangle counts?

Anyway, doing a bit of research, I've noticed that it's more traditional to use a line drawing technique that draws lines along edges that have a front facing and back facing triangle.

I realise that this technique would be more complex in terms of the code required (I'd have to collect and store all the edge-triangle information for a start, plus use a function to figure out which way a triangle is facing, vector math etc...) and also I am cautious that there may be limitations involved with doing this in Blitz. (E.g because you have draw the lines after all other rendering, you need to work out when not to draw them - if for example the object is behind something else)

So, basically my main question:

Is there anyone out there that would argue in favour of the traditional line-drawing method, and can give some tips for overcoming potential barriers such as the example mentioned, or should I just stick to the inverted mesh method?


Please no discussion on cel-shaded lighting for the moment, as I'm not quite ready to get into all that yet! :O)

Personally I like the sphere map method. Very fast, very simple. You just need a sphere map which has a black hollow circle filling the texture. I guess shade the inner circle with three or four shades of white and that would be a nice effect. It's not perfect but without pixel shaders nothing is.

IIRC, the best cel-shaded effect I ever saw was done by Mearrin, but I haven't seen him around in ages, and Blitzcoder, where he posted the pics, is gone now.

How do you apply the sphere map? Is it a lighting effect where you use a vector with the vertex normals to work out all the vertex UVs? That's just the sort of thing I didn't want to get into at this stage.

with thexture-flag 64 :]

Yeah, you literally just apply a texture with flag 64. The second texture channel should do it. ( Channel one, if zero is the first. )

Ah, now I understand. . . it's a simple texture mapping (well, simple from the blitz code end, probably complex in the underlying way it's actually applied)

It sounds cool and simple, and I might use it for the directional light shading, but. . . it has nothing to do with creating outlines!

Now, can we have some discussion on the topic I initially outlined please? :O)

Well if you're gonna get snotty, I won't tell you that what I just suggested takes care of the outline as well as the directional light shading ;o)

Sybix:
An edge outline created with a sphere map can get stretched out quite a bit and won't really look very good.

Also a sphere map is only good for very limited uses. Unless the light is directly overhead you can never move the camera, and if it is directly overhead you can't tilt the camera only rotate around the object. Otherwise the light appears to move. You need to make a cube map so the light stays in a fixed location regardless of how the camera is moved.

As for outlines, forget trying to make a mesh to represent 2D lines in realtime as the mesh changes. Drawing lines in 2d though... can't really say if that would be fast enough. Probably depends on the resolution and how many objects with lines there are in the scene. I can almost guarantee you though that for complicated scenes the inverted mesh will work best in the general case, and particularly on high end cards in high resolutions.

There is no way that drawing lines would be quick enough. Trust me. Stick with inverted-black-mesh method.

I've just been playing around with the idea of drawing lines. . .

So far I've just been drawing all edges on front facing triangles and so haven't needed to compile the list of edges etc. There does seem to be a perfomance hit, but only when you start drawing more than a few hundred lines.

It seems that the number of lines actually drawn is the main factor on performance, not the size of the mesh you perform the operation to (commenting out the Line statements proves this)

Here's the code:

Graphics3D 800, 600


Global mshSphere% = CreateSphere(12)
UpdateNormals mshSphere
EntityFX mshSphere, 4


Global GlobalLight% = CreateLight()
RotateEntity GlobalLight, 45, 45, 45
Global GlobalCamera% = CreateCamera()

PositionEntity GlobalCamera, 4, 2, 4
PointEntity GlobalCamera, mshSphere

CameraClsColor GlobalCamera, 180,180,180

Local fps%
Local fpscount%
Local millistop%
Local millis%

While Not KeyHit(1)
	Navigate_World_With_MouseAndKeys(0.5, 0.1)
	
	TurnEntity mshSphere, 0, 0.5, 0
	SetBuffer BackBuffer()
	Cls
	
	RenderWorld()
	DrawFrontFacingLines(mshSphere, GlobalCamera, 0, 0)
	Color 255, 0, 0
	Text 1, 1, "FPS=" + fps	
	Text 1, 12, "TrisRendered=" + TrisRendered()	
	
	Flip
	
	fpscount = fpscount + 1
	millis% = MilliSecs()
	If millistop < millis - 1000 Then
		millistop = millis
		fps = fpscount
		fpscount = 0
	End If
Wend
End


Function DrawFrontFacingLines(m%, cam, thick%, sketchy#)
	Color 30, 30, 50
	
	Local v3X = CreateVector(3)
	Local v3Y = CreateVector(3)		
	For is% = 1 To CountSurfaces(m)
		s% = GetSurface(m, is)
		For it% = 0 To CountTriangles(s) - 1
			If FrontFacing(cam, s, it, m) Then
				For i% = 0 To 2
					vx# = VertexX(s, TriangleVertex(s, it, i))
					vy# = VertexY(s, TriangleVertex(s, it, i))
					vz# = VertexZ(s, TriangleVertex(s, it, i))
					TFormPoint vx, vy, vz, m, 0
					vx = TFormedX()
					vy = TFormedY()
					vz = TFormedZ()
											
					CameraProject(cam, vx, vy, vz)
					VctPut v3X, i, ProjectedX()
					VctPut v3Y, i, ProjectedY()
				Next
				
				c0 = (VctGet(v3X,0)=0) And (VctGet(v3Y,0)=0)
				c1 = (VctGet(v3X,1)=0) And (VctGet(v3Y,1)=0)
				c2 = (VctGet(v3X,2)=0) And (VctGet(v3Y,2)=0)
				For n% = -thick To thick
					r# = sketchy
					If Not (c0 Or c1) Then Line VctGet(v3X,0)+n+Rnd(-r, r), VctGet(v3Y,0)+Rnd(-r, r), VctGet(v3X,1)+Rnd(-r, r), VctGet(v3Y,1)+Rnd(-r, r)
					If Not (c1 Or c2) Then Line VctGet(v3X,1)+n+Rnd(-r, r), VctGet(v3Y,1)+Rnd(-r, r), VctGet(v3X,2)+n+Rnd(-r, r), VctGet(v3Y,2)+Rnd(-r, r)
					If Not (c0 Or c2) Then Line VctGet(v3X,0)+n+Rnd(-r, r), VctGet(v3Y,0)+Rnd(-r, r), VctGet(v3X,2)+n+Rnd(-r, r), VctGet(v3Y,2)+Rnd(-r, r)
				Next

			End If
		Next
	Next
	DeleteVector v3X
	DeleteVector v3Y
End Function



Function Navigate_World_With_MouseAndKeys(turnSpeed#=1, moveSpeed#=1)
	Local dY# = EntityPitch(GlobalCamera)+MouseYSpeed()/2*turnSpeed
	If dY > 89 Then dY = 89
	If dY < -89 Then dY = -89
	
	Local dz# = (KeyDown(200)-KeyDown(208)) * moveSpeed
	Local dx# = (KeyDown(205)-KeyDown(203)) * moveSpeed
	If dz <> 0 And dx <> 0 Then 
		dx=dx * 0.707
		dz=dz * 0.707
	End If
	RotateEntity GlobalCamera, dY, EntityYaw(GlobalCamera)-(MouseXSpeed()/2)*turnSpeed, 0
	MoveEntity GlobalCamera, dx, 0, dz
	MoveMouse GraphicsWidth()/2, GraphicsHeight()/2
	
	If KeyHit(4) Then 
		CameraZoom GlobalCamera, 4.0
	End If
	If KeyHit(5) Then
		CameraZoom GlobalCamera, 1.0
	End If
End Function



Function FrontFacing%(cam%, s%, t%, m%)	
	Local v1 = CreateVector(3)
	Local v2 = CreateVector(3)
	Local v3 = CreateVector(3)
	
	
	x# = VertexX(s, TriangleVertex(s, t, 0))
	y# = VertexY(s, TriangleVertex(s, t, 0))
	z# = VertexZ(s, TriangleVertex(s, t, 0))
	TFormPoint x, y, z, m, cam
	VctPut v1, 0, TFormedX()
	VctPut v1, 1, TFormedY()
	VctPut v1, 2, TFormedZ()
	
	x# = VertexX(s, TriangleVertex(s, t, 1))
	y# = VertexY(s, TriangleVertex(s, t, 1))
	z# = VertexZ(s, TriangleVertex(s, t, 1))
	TFormPoint x, y, z, m, cam
	VctPut v2, 0, TFormedX()
	VctPut v2, 1, TFormedY()
	VctPut v2, 2, TFormedZ()
	
	x# = VertexX(s, TriangleVertex(s, t, 2))
	y# = VertexY(s, TriangleVertex(s, t, 2))
	z# = VertexZ(s, TriangleVertex(s, t, 2))
	TFormPoint x, y, z, m, cam
	VctPut v3, 0, TFormedX()
	VctPut v3, 1, TFormedY()
	VctPut v3, 2, TFormedZ()
	
	
	Local vEdge1 = V3dSubtract(v3, v1)
	Local vEdge2 = V3dSubtract(v3, v2)
	
	Local vFNormal = V3dCross(vEdge1, vEdge2)
	
	Local bFrontFacing% = (V3dDot(v1, vFNormal) < 0)
	
	DeleteVector v1
	DeleteVector v2
	DeleteVector v3
	DeleteVector vEdge1
	DeleteVector vEdge2
	DeleteVector vFNormal
	
	Return bFrontFacing
End Function



Function V3dAdd(v1, v2)
	Local v3 = CreateVector(3)
	
	VctPut v3, 0, VctGet(v1,0) + VctGet(v2,0)
	VctPut v3, 1, VctGet(v1,1) + VctGet(v2,1)
	VctPut v3, 2, VctGet(v1,2) + VctGet(v2,2)
	
	Return v3
End Function


Function V3dSubtract(v1, v2)
	Local v3 = CreateVector(3)
	
	VctPut v3, 0, VctGet(v1,0) - VctGet(v2,0)
	VctPut v3, 1, VctGet(v1,1) - VctGet(v2,1)
	VctPut v3, 2, VctGet(v1,2) - VctGet(v2,2)
	
	Return v3
End Function


Function V3dCross(v1, v2)
	Local v3 = CreateVector(3)
	
	VctPut v3, 0, VctGet(v1,1)*VctGet(v2,2) - VctGet(v1,2)*VctGet(v2,1)
	VctPut v3, 1, VctGet(v1,2)*VctGet(v2,0) - VctGet(v1,0)*VctGet(v2,2)
	VctPut v3, 2, VctGet(v1,0)*VctGet(v2,1) - VctGet(v1,1)*VctGet(v2,0)
	
	Return v3
End Function


Function V3dDot#(v1, v2)
	Return VctGet(v1,0)*VctGet(v2,0) + VctGet(v1,1)*VctGet(v2,1) + VctGet(v1,2)*VctGet(v2,2)
End Function



Function VctGet#(v, i%)
	Return PeekFloat(v, i Shl 2)
End Function




Function VctPut(v, i%, val#)
	PokeFloat v, i Shl 2, val
End Function


Function CreateVector(nDim%)
	v% = CreateBank(nDim Shl 2)
	Return v
End Function


Function DeleteVector(v)
	FreeBank v
End Function

Yup, I think after experimenting I'm inclined to agree. However, I think that some more interesting effects might be achievable with line drawing. . . for example, try modifying the code above to pass in a value of 1 or 2 to the sketchy parameter in the DrawFrontFacingLines function to see what I mean. . .


So far I'm still not sure which way is best, but I'm starting to see the pros and cons of each. Also, I still have no idea how to solve the problem of deciding whether or not to draw lines based on whether an edge is hidden behind something or not.

Thanks people. . . keep the ideas coming :O)

Ooh. I just noticed that my FPS sometimes keeps going up and down in a cycle as the sphere turns. I am clueless as to why this happens. . . does this happen for anyone else with the above code?

Anyone got any idea why this would happen???

Also, just noticed that the length of the lines has a major effect on performance (move closer and the FPS goes down)

I guess that means that it's just down to the number of pixels that have to be written to the screen that causes the performance limit. . .

I think I just answered my own question! :O)

The major performance is the drawing the with your example above. This is because, a) you are drawing lots of lines :D and b) you aren't doing much calculation.

If this were a true algorithm for edge detection it would be very slow (probably slower) but mostly cos of the maths involved.

Yes, I wouldn't be doing a full-edge detection because that would be silly . . it normally takes at least couple of seconds to apply such a filter to a desktop sized image, because it's a raster effect and has to be applied to ALL pixels on screen. I'm dealing with vectors and line drawing, not raster filters here. . .

I don't think that I'll be doing much more calculation when I add the part that checks for edges with a front facing + back facing triangle next to it, at least not enough more for it to have a major perfomance hit.

I do however think that any attempt to 'cull' the line drawing based on whether a line is behind an object or not might be heavy on the calculations.

Hmmm. Here's a thought - perhaps I could combine a raster-edge detection with the line drawing method: Use the line technique to decide where on screen to apply the edge detection. That way the edge-detection is only applied to a small portion of the screen... it would solve the lines behind an object problem completely!

I bet it would be really slow, but I think its probably going to be a fun experiment. . . :O)

I would leave the Line command well alone as it's very slow, relatively speaking.

However, if you're determined to use real lines, you could try using 3D lines. Here's a function for 3D lines:

;
; Adds a 3D line to the specified mesh.
; Note: 3D lines are only properly visible when rendered in wireframe mode!
; 
; Params:
; mesh     - Mesh to add 3D line to. If 0, a new mesh is created.
; x0,y0,z0 - Start point of line.
; x1,y2,z1 - End point of line.
; r,g,b    - Line colour.
;
; Returns:
; Handle of mesh the 3D line was added to.
;
Function create_3D_line(mesh,x0#,y0#,z0#,x1#,y1#,z1#,r%=255,g%=255,b%=255) 

	If mesh = 0 
		mesh = CreateMesh() 
		surf = CreateSurface(mesh) 
		EntityFX mesh,1+2+16
	Else 
		last_surf = CountSurfaces(mesh)
		surf = GetSurface(mesh,last_surf)
		If CountVertices(surf) > 30000 Then surf = CreateSurface(mesh)
	End If 

	v0 = AddVertex(surf,x0,y0,z0) 
	v1 = AddVertex(surf,x1,y1,z1)  
	v2 = AddVertex(surf,x0,y0,z0)  
	AddTriangle surf,v0,v1,v2
	
	VertexColor surf,v0,r,g,b
	VertexColor surf,v1,r,g,b
	VertexColor surf,v2,r,g,b

	Return mesh 

End Function

Using this method you have to do 2 renders: one normal render then one render in WireFrame mode to display the 3D line mesh. I've used this technique in the past and it's pretty fast.

Yep, this would be ideal.
The only problem is, as you say I have to do 2 renders, and there would be no easy way to 'choose' which lines to draw (eg don't draw ones behind objects and only ones that are along front+back facing triangles).

This sort of thing is fine in C++ or whatever because we have access to the directx functions and can render whatever, whenever we chose. But we only get limited options with this kind of thing in Blitz because it's all done for us. . .

Please, someone - tell me I'm wrong because I would love to make this as easy and fast as possible :O)

Not sure what you mean by that - can you explain a bit more?

We can render what we want, when we want in Blitz3D too, can't we?

Don't be put off by doing multiple renders. Many people use this technique for various effects. By only showing stuff you want in a particular render, and hiding everything else, it's not going to be much (if any) slower than rendering everything in one go.

As for determining which lines need drawing, I think this is going to involve some pretty heavy math whichever way you look at it. That's why the folks above have been advocating the spheremap method. :)

Isn't it possible with directx to choose to only draw specific triangles, or edges? I've hardly used c++ with directx before, but that was the kind of impression I was getting when I was reading up on these cel shading techniques. . .

Also, hiding and showing entities, is pretty tedious code wise. . . I wish I could just have the option of Render this, or render that :O)

You misunderstand me. I wasn't talking about raster edge detection.

Actually I think I misunderstood your code, I didn't actually look to see if it were doing some edge detection, and thinking about it you can draw millions of lines with little slowdown in Blitz. So, the biggest bottleneck is already the maths.

That's not what I'm finding. . . the maths is fast. It's the Line function that's using up all the time. . .

Is there a faster way of drawing 2d lines that I'm unaware of?

Perhaps I could lock the buffer and draw all of the lines using fast pixel writing before unlocking it again. Would this be faster than repeatingly calling the Line function?

You can try cacheing the line data. And then drawing them all inside a Locked/UnLockBuffer() setup.

Not sure if that will help cos of the extra overhead of cacheing the data.

I also noticed you are drawing too many lines. Change this function below (notice I commented out one line):

Function DrawFrontFacingLines(m%, cam, thick%, sketchy#)
	Color 30, 30, 50
	
	Local v3X = CreateVector(3)
	Local v3Y = CreateVector(3)		
	For is% = 1 To CountSurfaces(m)
		s% = GetSurface(m, is)
		For it% = 0 To CountTriangles(s) - 1
			If FrontFacing(cam, s, it, m) Then
				For i% = 0 To 2
					vx# = VertexX(s, TriangleVertex(s, it, i))
					vy# = VertexY(s, TriangleVertex(s, it, i))
					vz# = VertexZ(s, TriangleVertex(s, it, i))
					TFormPoint vx, vy, vz, m, 0
					vx = TFormedX()
					vy = TFormedY()
					vz = TFormedZ()
											
					CameraProject(cam, vx, vy, vz)
					VctPut v3X, i, ProjectedX()
					VctPut v3Y, i, ProjectedY()
				Next
				
				c0 = (VctGet(v3X,0)=0) And (VctGet(v3Y,0)=0)
				c1 = (VctGet(v3X,1)=0) And (VctGet(v3Y,1)=0)
				c2 = (VctGet(v3X,2)=0) And (VctGet(v3Y,2)=0)
				For n% = -thick To thick
					r# = sketchy
					If Not (c0 Or c1) Then Line VctGet(v3X,0)+n+Rnd(-r, r), VctGet(v3Y,0)+Rnd(-r, r), VctGet(v3X,1)+Rnd(-r, r), VctGet(v3Y,1)+Rnd(-r, r)
					If Not (c1 Or c2) Then Line VctGet(v3X,1)+n+Rnd(-r, r), VctGet(v3Y,1)+Rnd(-r, r), VctGet(v3X,2)+n+Rnd(-r, r), VctGet(v3Y,2)+Rnd(-r, r)
;					If Not (c0 Or c2) Then Line VctGet(v3X,0)+n+Rnd(-r, r), VctGet(v3Y,0)+Rnd(-r, r), VctGet(v3X,2)+n+Rnd(-r, r), VctGet(v3Y,2)+Rnd(-r, r)
				Next

			End If
		Next
	Next
	DeleteVector v3X
	DeleteVector v3Y
End Function

Why did you remove that line? I have to draw 3 lines - a triangle has 3 lines. . . doesn't it?

I'm confused??? :O)


Also, remember that when I add the filtering part that only draws lines on edges that have a front facing and back facing triangle, there will be only a fraction of the lines drawn.



I wouldn't have to - I could lock the buffer at the start of the whole function and not unlock until the end. The lines would still be drawn on the fly. . .

. . . or wait, does locking the buffer mean you can't use any Blitz3d commands such as CameraProject etc?
I thought it was just rendering commands (i.e ones that write or read pixel values to graphics buffers) that are affected. I think I'll ask this in a new post actually. . .

I removed a line cos if you draw 3 lines for every triangle, you will be drawing each line twice. Think about it, or even better just try it.

No, I still don't get you. . .
Unfortunately I can't try it until tonight, cos I don't have access to Blitz Basic right now.

I still think you are wrong though - when I draw a triangle on paper there are most definitely 3 lines to draw. And logically, if you have 3 vertices v0, v1 and v2 then you have these 3 different lines to draw:
1) v0 to v1
2) v1 to v2
3) v0 to v2

The line you removed was v0-v2, for some reason. . .?

Ah, now wait a second. . . I see what you mean. duh!
I wasn't thinking of triangles joined together. . .

You win! :O)

Actually, this will all be taken in to control when I build in the edge data - I will make sure each edge is listed once and only once, with the 2 triangles linked by reference. I'll probably use some kind of array:
edgeTriangle(v1, v2, triangle)
where triangle can be 0 or 1, and the size of dimensions v1 and v2 total the number of vertices in the mesh.

Actually this might be dumb because most of the array won't be used and I certainly won't want to loop through all of it. . . I'll figure something out, perhaps another Bank :O)

Stick to the inverted mesh method with spherical mapping of a gradient texture... much faster , easy to implement etc... The method you're attempting is going to be far too slow to be practical in a game ( especially the occlusion part ) .... but I guess you're realising this now?

Yep. I'm realising this, but I'm still going to try out my outline-limited edge detection idea, just because it would be fun and might look cool - even if it only renders 3 frames per second :O)

This has been researched to death in Blitz. For outlines, you want the inverted mesh approach.

Trouble is, the inverted mesh approach looks horrible.

I agree that the inverted mesh method doesn't always look good but alot of that depends on how the mesh is created in the first place. Convex shapes with no overlapping polys will give you good results.

If the method you're going to use involved drawing lines over the top of the mesh ... surely they'll need to be a decent thickness to have the desired effect?

There is no reason why the inverted mesh method shouldn't look good, as long as you aren't just inverting the mesh and scaling it.

Well, it will look okay, most of the time. . . but:

1) there's the problem of consistency in the thickness / visibility of the lines (something far away will have lines that are really thin and disappearing)

2) you can't decide exactly where you want to draw the lines, even though most of the time they appear in the right place. But what if you wanted to always outline certain edges, and not others?

3) There's the problem getting nice smooth lines, that are antialiased. . . (You can do this with line drawing, although it would take a lot of processing time)

I do admit, that if I'm going to be working in a real time game with lots of cel shading going on, I'll probably use the flip mesh. But I still want to experiment with other ways and see what kind of cool alternative effects I can create for quickly rendering a video sequence.

I think that line drawing will prove to be a much more flexible and artistically useful technique, even if it's too slow for real time. It's still going to be hundreds of times faster than doing full-blown edge detections on the whole screen! :O)

1. You can rescale the outline mesh based on it's distance to the camera if you want a consistent thickness. Very easy.

2. You could use Vertex colours to always outline certain edges or even include this in the texture itself ... may not look too good though.

Don't get me wrong I'm not trying to be negative here .. good luck to you .. I'm sure we'd all be interested in your results.

Scaling the outline mesh would have to be done vertex by vertex, and that wouldn't be acceptable for realtime. Though if you wanted to waste the video ram you could preprepare a few widths, each half the size of the previous and switch as objects move into the distance. But that would only work if you used two seperate meshes. Unless maybe you had multiple surfaces and used alpha... Hopefully you wouldn't get a surface hit for surfaces with alpha 0.

As for antialised lines, they'll be antialiased if you have full screen antialiasing on. Otherwise, you're out of luck. Why would you want the lines to be antialised if your polygon edges aren't though? It would look weird.

If you want to make a cel shaded game which doesn't just use the mesh outline method, what you really need is pixel shaders. So maybe you'll have to wait for Max3D to come along. Then you'll be able to get exactly the effect you want.

Roll on Max3d then. . . :O)



I think I'd have to do it manually because I'm starting to use fast pixel writing to draw the lines all in one go. Also, I'm thinking of doing localised edge-detection, which if I make sophisticated enough, should antialias automatically anyway. This is the experiment I'm working on. I do expect to be really slow - so you don't have to warn me :O)


thanks!

Why don't you just draw the lines using single-surface quads. You can make really good soft edged lines using this aproach and it's fast. Just use small gradient texsturemap with the quads and stretch/resize one to make a line. This way you can't blame the line drawing when your algo is too slow :)

thats what i was going to say after only reading the first post.

Drawing the lines isn't really the bottleneck - it's calculating where to draw them that is.