A better UpdateNormals()

This averages the normals of every triangle connected to a vertex. Unless all your vertices are totally merged, this will make flat faces correctly. Merged vertices will appear more rounded.

Function UpdateNormals(mesh)
For s=1 To countsurfaces(mesh)
	surf=getsurface(mesh,s)
	For v=0 To CountVertices(surf)-1
		
		nx#=0.0
		ny#=0.0
		nz#=0.0
		triscount=0
		
		For t=0 To CountTriangles(surf)-1
		
			a=TriangleVertex(surf,t,0)
			b=TriangleVertex(surf,t,1)
			c=TriangleVertex(surf,t,2)
			If a=v Or b=v Or c=v
			
				Ax#=VertexX(surf,a)
				Ay#=VertexY(surf,a)
				Az#=VertexZ(surf,a)
				TFormPoint Ax,Ay,Az,mesh,0
				Ax=TFormedX()
				Ay=TFormedY()
				Az=TFormedZ()
				
				Bx#=VertexX(surf,B)
				By#=VertexY(surf,B)
				Bz#=VertexZ(surf,B)
				TFormPoint Bx,By,Bz,mesh,0
				Bx=tformedx()
				By=tformedy()
				Bz=tformedz()
				
				Cx#=VertexX(surf,C)
				Cy#=VertexY(surf,C)
				Cz#=VertexZ(surf,C)
				TFormPoint Cx,Cy,Cz,mesh,0
				Cx=tformedx()
				Cy=tformedy()
				Cz=tformedz()
		
				ux#=Bx-Ax
				uy#=By-Ay
				uz#=Bz-Az
				vx#=Cx-Ax
				vy#=Cy-Ay
				vz#=Cz-Az   

				x#=(uy*vz)-(uz*vy)
				y#=(uz*vx)-(ux*vz)
				z#=(ux*vy)-(uy*vx)

				nx=nx+x
				ny=ny+y
				nz=nz+z
				triscount=triscount+1

				EndIf

			Next

		l#=Sqr(nx^2+ny^2+nz^2)
		nx=nx/l
		ny=ny/l
		nz=nz/l
		tformvector nx,ny,nz,0,mesh
		VertexNormal surf,v,TFormedX(),TFormedY(),TFormedZ()
		
		Next
	Next
End Function

You can leave out all the TForm commands and instead of using x^2 it's a good idea to use x*x as it is much much faster. So here is the same function with a few modifications:

Function UpdateNormals(mesh)
	For s=1 To CountSurfaces(mesh)
		surf=GetSurface(mesh,s)
		For v=0 To CountVertices(surf)-1
			nx#=0.0
			ny#=0.0
			nz#=0.0
			For t=0 To CountTriangles(surf)-1
				a=TriangleVertex(surf,t,0)
				b=TriangleVertex(surf,t,1)
				c=TriangleVertex(surf,t,2)
				If a=v Or b=v Or c=v
					Ax#=VertexX(surf,a)
					Ay#=VertexY(surf,a)
					Az#=VertexZ(surf,a)
					Bx#=VertexX(surf,B)
					By#=VertexY(surf,B)
					Bz#=VertexZ(surf,B)
					Cx#=VertexX(surf,C)
					Cy#=VertexY(surf,C)
					Cz#=VertexZ(surf,C)
					ux#=Bx-Ax
					uy#=By-Ay
					uz#=Bz-Az
					vx#=Cx-Ax
					vy#=Cy-Ay
					vz#=Cz-Az   
					x#=(uy*vz)-(uz*vy)
					y#=(uz*vx)-(ux*vz)
					z#=(ux*vy)-(uy*vx)
					nx=nx+x
					ny=ny+y
					nz=nz+z
				EndIf
			Next
			l#=Sqr(nx*nx+ny*ny+nz*nz)
			nx=nx/l
			ny=ny/l
			nz=nz/l
			VertexNormal surf,v,nx,ny,nz
		Next
	Next
End Function

Good job Halo!

Fredborg

I already released a function which is in the code archives which does this same thing.

Your function has to loop through every triangle in the mesh once for every vertex in the mesh, and check to see if the vertex is in that triangle. It then has to calculate the face normal of each triangle three times, once for each vertex in the triangle.

My function calculates the face normal of each traingle in the mesh, stores these, and at the same time, stores the triangles which are connected to each vertex. It then calculates the vertex normals using these face normals and connected triangle lists.

My function costs you some ram, but in theory it should be significantly faster.

Who cares? UpdateNormals() isn't something you should be doing except once when you load or make something.

Yeah, we're into that weird area where programmers spent tons of time and brain cycles optimizing code that only runs occasionally.

I see...

So nobody here ever creates a model, like say oh, I don't know, WATER, which changes every frame and needs to have it's normals recalculated?

Or say, oh, I don't know, like, oh, your own skeletal animation system which moves thousands of vertices every frame based on the influences of specific bones?

And of course nobody cares about an additional 2 seconds of load time when performing this operation on a mere 50K-100K polygons.

There are lots of potnetial instances where being faster in this particular function could be well worth it. Personally, I think it's worth shaving two seconds off your load times.

And two seconds is no exxageration. I just tested Halo's code against my own code, and Blitz's function. My code is 19x faster than Halo's function and 16x slower than Blitz's function.

Hm... I'm wondering if the whole reason Mark does what he does is for speed/memory, and not because it is the best way to smooth a model. But how could that be... he has to physically check to see if other vertices are at the same location in space. Damn that must be slow. How much faster would the internal updatenormals function be if it ignored such verticeslike our own functions?

Anyhow, I'm going off topic. It is definitely not worthless to optimize this function. Two seconds at load is a significant amount of time. Load times are already long enough as it is. With your sort of attitutde it's no wonder it takes almost a minute for Windows 98 to load on my system! :-)

Every little bit helps, and two seconds is not such a small sliver of time that it's not worth doing.


My test was run on my 2ghz Athalon, and in it Halo's function took 1.25 seconds to execute. My own function took 0.065 seconds. That was with 50K polygons. I'm assuming that there's quite a few poeple out there with slower systems and that many games will use that many polygons in their level alone. So I doubled the speed hit in my 2 second example above to account for that.


Here is the test code. Try it for yuorself, feel free to report your results. I don't doubt that you two probably have better systems than I and will blow through this test a lot faster, but that still doesn't mean you wouldn't see real framerate benefits in the game for using a faster function when doing effects which require mesh deformation... Though for that particular purpouse I suppose I will have to reccomend Blitz's own function, as that is by far the fastest. So I guess the real benefit here is where I assume Halo uses his function, and where I use mine, which is when the level, decorative, and powerup models are loaded.

Dim Face_NX#(32768)
Dim Face_NY#(32768)
Dim Face_NZ#(32768)
		
Dim Vertex_ConnectedTris(32768)
Dim Vertex_TriList(32768, 32)


Mesh = CreateSphere(16)

StartTime = MilliSecs()
For Loop = 0 To 51
	;UpdateNormals(Mesh) 		; Blitz
	;UpdateNormals2(Mesh) 		; Halo
	Calculate_Normals(Mesh) 	; Shawn
Next

EndTime = MilliSecs()

Print Str$(Float(EndTime-StartTime) / 1000.0) + "seconds"

WaitKey()

End


Function UpdateNormals2(mesh)

For s=1 To CountSurfaces(mesh)

surf=GetSurface(mesh,s)

For v=0 To CountVertices(surf)-1

nx#=0.0

ny#=0.0

nz#=0.0

For t=0 To CountTriangles(surf)-1

a=TriangleVertex(surf,t,0)

b=TriangleVertex(surf,t,1)

c=TriangleVertex(surf,t,2)

If a=v Or b=v Or c=v

Ax#=VertexX(surf,a)

Ay#=VertexY(surf,a)

Az#=VertexZ(surf,a)

Bx#=VertexX(surf,B)

By#=VertexY(surf,B)

Bz#=VertexZ(surf,B)

Cx#=VertexX(surf,C)

Cy#=VertexY(surf,C)

Cz#=VertexZ(surf,C)

ux#=Bx-Ax

uy#=By-Ay

uz#=Bz-Az

vx#=Cx-Ax

vy#=Cy-Ay

vz#=Cz-Az   

x#=(uy*vz)-(uz*vy)

y#=(uz*vx)-(ux*vz)

z#=(ux*vy)-(uy*vx)

nx=nx+x

ny=ny+y

nz=nz+z

EndIf

Next

l#=Sqr(nx*nx+ny*ny+nz*nz)

nx=nx/l

ny=ny/l

nz=nz/l

VertexNormal surf,v,nx,ny,nz

Next

Next

End Function





; -------------------------------------------------------------------------------------------------------------------
; This function calculates and sets the normals for a mesh.
;
; Should probably update this so that it can recursively loop through all of an entities children as well.
; -------------------------------------------------------------------------------------------------------------------
Function Calculate_Normals(ThisMesh)
	
	; Loop through all surfaces of the mesh.
	Surfaces = CountSurfaces(ThisMesh)
	For LOOP_Surface = 1 To Surfaces

		Surface_Handle = GetSurface(ThisMesh, LOOP_Surface)

		; Reset the number of connected polygons for each vertex.
		For LoopV = 0 To 32767	
			Vertex_ConnectedTris(LoopV) = 0
		Next	
	
		; Loop through all triangles in this surface of the mesh.
		Tris = CountTriangles(Surface_Handle)
		For LOOP_Tris = 0 To Tris-1

			; Get the vertices that make up this triangle.
				Vertex_0 = TriangleVertex(Surface_Handle, LOOP_Tris, 0)
				Vertex_1 = TriangleVertex(Surface_Handle, LOOP_Tris, 1)
				Vertex_2 = TriangleVertex(Surface_Handle, LOOP_Tris, 2)
	
			; Adjust the number of triangles each vertex is connected to and
			; store this triangle in each vertex's list of triangles it is connected to.
				ConnectedTris = Vertex_ConnectedTris(Vertex_0)
				Vertex_TriList(Vertex_0, ConnectedTris) = LOOP_Tris
				Vertex_ConnectedTris(Vertex_0) = ConnectedTris + 1

				ConnectedTris = Vertex_ConnectedTris(Vertex_1)
				Vertex_TriList(Vertex_1, ConnectedTris) = LOOP_Tris
				Vertex_ConnectedTris(Vertex_1) = ConnectedTris + 1

				ConnectedTris = Vertex_ConnectedTris(Vertex_2)
				Vertex_TriList(Vertex_2, ConnectedTris) = LOOP_Tris
				Vertex_ConnectedTris(Vertex_2) = ConnectedTris + 1

			; Calculate the normal for this face.

				; Get the corners of this face:
				Ax# = VertexX#(Surface_Handle, Vertex_0)
				Ay# = VertexY#(Surface_Handle, Vertex_0)
				Az# = VertexZ#(Surface_Handle, Vertex_0)

				Bx# = VertexX#(Surface_Handle, Vertex_1)
				By# = VertexY#(Surface_Handle, Vertex_1)
				Bz# = VertexZ#(Surface_Handle, Vertex_1)

				Cx# = VertexX#(Surface_Handle, Vertex_2)
				Cy# = VertexY#(Surface_Handle, Vertex_2)
				Cz# = VertexZ#(Surface_Handle, Vertex_2)

				; Triangle 1
				; Get the vectors for two edges of the triangle.
				Px# = Ax#-Bx#
				Py# = Ay#-By#
				Pz# = Az#-Bz#

				Qx# = Bx#-Cx#
				Qy# = By#-Cy#
				Qz# = Bz#-Cz#

				; Compute their cross product.
				Nx# = Py#*Qz# - Pz#*Qy#
				Ny# = Pz#*Qx# - Px#*Qz#
				Nz# = Px#*Qy# - Py#*Qx#

				; Store the face normal.
				Face_NX#(LOOP_Tris) = Nx#
				Face_NY#(LOOP_Tris) = Ny#
				Face_NZ#(LOOP_Tris) = Nz#

		Next

		; Now that all the face normals for this surface have been calculated, calculate the vertex normals.
		Vertices = CountVertices(Surface_Handle)
		For LOOP_Vertices = 0 To Vertices-1

			; Reset this normal.
			Nx# = 0
			Ny# = 0
			Nz# = 0

			; Add the normals of all polygons which are connected to this vertex.
			Polys = Vertex_ConnectedTris(LOOP_Vertices)
				
			For LOOP_Polys = 0 To Polys-1

				ThisPoly = Vertex_TriList(LOOP_Vertices, LOOP_Polys)

				Nx# = Nx# + Face_NX#(ThisPoly)
				Ny# = Ny# + Face_NY#(ThisPoly)
				Nz# = Nz# + Face_NZ#(ThisPoly)			
				
			Next	
				
			; Normalize the new vertex normal.
			; (Normalizing is scaling the vertex normal down so that it's length = 1)

				Nl# = Sqr(Nx#^2 + Ny#^2 + Nz#^2)

				; Avoid a divide by zero error if by some freak accident, the vectors add up to 0.
				; If Nl# = 0 Then Nl# = 0.1

				Nx# = Nx# / Nl#
				Ny# = Ny# / Nl#
				Nz# = Nz# / Nl#

			; Set the vertex normal.
			
				VertexNormal Surface_Handle, LOOP_Vertices, Nx#, Ny#, Nz#
				;VertexColor Surface_Handle, LOOP_Vertices, polys*127, polys*127, polys*127
		
		Next

	Next

End Function

"Yeah, we're into that weird area where programmers spent tons of time and brain cycles optimizing code that only runs occasionally."

Or waste a couple hours writing a function which someone else has already written?



...Not that is is really a waste, assuming one needs to learn how normals are calculated. Nothing like writing your own function to teach you that.

You use Win98 and want to lecture me on optimization? Begone, good sir. :)

cool, I dont have to write that code.
8)

Nice work halo/sswift. The above routine I think is a better general purpose routine than Blitz's own, however Blitz's routine will give triangulated meshes (i.e. no shared vertices) a smoother appearance than the above one.

Also, the above routine reveals 'seems' when used on Blitz's built-in primitives, whereas Blitz3D's doesn't.

Uh oh, I offended someone again.

Yeh, that's normal.

I was not offended.

I just think it was silly of you to write a slower version of the same exact function I posted in the code archives a year ago.

And claiming that it's pointless to spend the effort on opimizing it... Well, what effort? I just gave you the optimized version for free. :-)



"Also, the above routine reveals 'seems' when used on Blitz's built-in primitives, whereas Blitz3D's doesn't."

Yeah I noticed that myself.

That is the result of an unfortunate issue. You see, anywhere where there is a discontinuity in texture coordinates, you have to have extra vertices. This may also be why Mark chose to code his updatenormals function in the way that he did.

Imagine wrapping a texture around a cylinder. You start out at 0, increment as you go around 360 degrees, and when you arrive back at the start you have a coordinate of 1. The jump to 0 from 1 would put a whole flipped copy of the texture at that point. That's a dicontinuity. So you have to just make extra vertcies there.

Since all of Blitz's primitives have textures wrapped around them, they all have problems when shaded with a function like the ones above.

Unfortunately, there is no way to fix this problem that I can see. No automatic normal generation functions can solve this issue. There will always be surfaces which are realtively angular which you want smoothed over, and realtive smooth surfaces which you want to look faceted, and you can't assume that any time a vertex has another vertex on top of it that they should be smoothed, and you can't even check to see if they have a texture discontinuity to make that decision because of objects like cubes.

The only way to "solve" this whole thing that I can see is to give surfaces so many polygons that you no longer need to even bother approximating the shading with vertex normals. And obviously we're nowhere near that point yet.

"Yeh, that's normal."

Is that supposed to be punny? :-)

hmm... sswift, maybe halo didn't even notice it?

"hmm... sswift, maybe halo didn't even notice it?"

Well duh. :-)

battle of the egos.... keep going guys, you usre do make these boards a fun place to read.... not..

I try not to look at the code archives.

Actually Wiebo, i find threads like this fun to read.. breaks away from the normal stuff you read on these forums.

Tracer

No pun intended?

The only time you can get a normals generating system to smooth correctly is when it is working on an exporter. The Lightwave convertor uses the surface smoothing angle property to smooth polys which are at an angle to eachother less than the the spec and separates ones that are above the angle range.

Ideally Blitz brushes/surfaces should have a 'Smoothing Angle' property (or something like it), so that UpdateNormals can smooth accordingly.