Calculating Normals Speed Tips

BlitzMax Forums/BlitzMax Programming/Calculating Normals Speed Tips

eizdealer

(Posted 2005) [#1]

Hi there
Playing around a little with OpenGL and 3D maths I've encountered a problem. It appears when calculating normals for a mesh. I don't know exactly whether my code is bad (the results are OK though), it is a beta problem or calculating normals just takes a looong time.
Maybe you can give me some hints on how to optimize my code.
The problem is calculating smoothed normals in particular. But now the code extract from the UpdateNormals method that causes me headache (won't run alone):

'Step 2: look whether a normal is affected by a neighbor
If Smooth Then
	Local Vert:eeVertex 'vertex type
	Local OtherVertices:Int 'number of vertices that have the same X/Y/Z coords like the current vertex +1
	For Local T:Int = 0 To Self.TriangleCount -1 'mesh trianglecount
		For Local V:Int = 0 To 2 'vertices
			
			'check every single vertex
			Vert = Self.TriangleData[T].V[V] 'get current vertex
			
			OtherVertices = 1 'reset
			
			'for every all other triangle's vertices
			For Local T2:Int = 0 To Self.TriangleCount -1
				Local Triangle:eeTriangle = Self.TriangleData[T2]
				If Triangle <> Self.TriangleData[T] Then 'if the triangles are not the same
					'if the coords are the same with any of the triangles vertices
					If (Abs(Vert.X-Triangle.V[0].X) + Abs(Vert.Y-Triangle.V[0].Y) + Abs(Vert.Z-Triangle.V[0].Z) <= .0) Or ..
					   (Abs(Vert.X-Triangle.V[1].X) + Abs(Vert.Y-Triangle.V[1].Y) + Abs(Vert.Z-Triangle.V[1].Z) <= .0) Or ..
					   (Abs(Vert.X-Triangle.V[2].X) + Abs(Vert.Y-Triangle.V[2].Y) + Abs(Vert.Z-Triangle.V[2].Z) <= .0) Then
					   OtherVertices :+ 1 'mark that a normal has been added
					   Vert.NX = Vert.NX + Triangle.NX
					   Vert.NY = Vert.NY + Triangle.NY
					   Vert.NZ = Vert.NZ + Triangle.NZ
					EndIf
							   
				EndIf
			Next
			
			'divide the normal parts through the count of normals that have affected the data
			Vert.NX :/ Float(OtherVertices) ; Vert.NY :/ Float(OtherVertices) ; Vert.NZ :/ Float(OtherVertices)
					
		Next
	Next
EndIf

I've tested it with a single 2048 poly mesh and this part of the method takes >3.3 seconds (on a 2.8 ghz p4!). On the other hand it is quite costly because you have to iterate all vertices and then iterate all vertices for every single vertex again, which makes a total of 2048*3*(2048-1)*3 = 37,730,304 vertices that have to be checked.
I thought 'OK, let's turn off the debug mode' but things got worse. It suddenly took >4.5 seconds (!!).

So my questions are: Is there a way to optimize the code? How did Blitz3D do it? How do other engines do it? Will that debug thingy get fixed?

By the way - please ignore all grammar errors ;)

fredborg

(Posted 2005) [#2]

It looks like you are over complicating it. The following pseudo code, shows a simpler way:

For Every Vertex
 NormalX = 0.0
 NormalY = 0.0
 NormalZ = 0.0
Next

For Every Triangle
 CalculateNormal
 For Every Vertex Used By Triangle
  NormalX :+ TriangleNormalX
  NormalY :+ TriangleNormalY
  NormalZ :+ TriangleNormalZ
 Next
Next

For Every Vertex
 NormalLength = SquareRoot (NormalX^2 + NormalY^2 + NormalZ^2)
 NormalX :/ NormalLength
 NormalY :/ NormalLength
 NormalZ :/ NormalLength
Next

eizdealer

(Posted 2005) [#3]

That's just for common normals, not for smoothed ones :)

fredborg

(Posted 2005) [#4]

What? Surely you don't want to smooth across non-shared vertices?

And if you for some reason do, it's a simple matter of making a cross-reference list before calculating the normals.

AntonyWells

(Posted 2005) [#5]

If all else fails, try this. Use it myself on a p2-350 without any slow down on bigger meshes.

	Local VCon:Double[ vIndex +3];
				
				While Index<vIndex
					
					Norms[Index]=0
					Index:+1
				
				Wend
				
				Index = 0
				
				While Index<TIndex
							
					V0 = Tris[ Index ] 
					V1 = Tris[ Index +1 ] 
					V2 = Tris[ Index +2 ] 
					
					Vec1.Set3D( Verts[ V0*3],Verts[ V0*3+1],Verts[ V0*3+2] )
					Vec2.Set3D( Verts[ V1*3],Verts[ V1*3+1],Verts[ V1*3+2] )
					Vec3.Set3D( Verts[ V2*3],Verts[ V2*3+1],Verts[ v2*3+2] )
					
					VecB1.CoPlaner( Vec1,Vec2 )
					VecB2.CoPlaner( Vec1,Vec3 )
			
					Norm.DotProduct3D( VecB1,VecB2 ) 
					Norm.Normalize()
					
					TNorms[ Index ] = Norm.Vec[0]
					TNorms[ Index+1 ] = Norm.Vec[1]
					TNorms[ Index+2 ] = Norm.Vec[2]
					
					VCon[V0]:+1
					VCon[V1]:+1
					VCon[V2]:+1
					
					Norms[ V0*3]:+Norm.Vec[0]
					Norms[ V0*3+1]:+Norm.Vec[1]
					Norms[ V0*3+2]:+Norm.Vec[2]
					
					Norms[ V1*3]:+Norm.Vec[0]
					Norms[ V1*3+1]:+Norm.Vec[1]
					Norms[ V1*3+2]:+Norm.Vec[2]
					
					
					Norms[ V2*3]:+Norm.Vec[0]
					Norms[ V2*3+1]:+Norm.Vec[1]
					Norms[ V2*3+2]:+Norm.Vec[2]
					
												
					Index:+3
					
				Wend
				
				Index=0
				Local CIndex:Int
								
				While Index<vIndex
					
					If VCon[Index] = 0 VCon[Index]=0.0001
					
					Norm.Set3D( Norms[Index]/VCon[CIndex],Norms[Index+1]/VCon[CIndex],Norms[Index+2]/Vcon[CIndex])
					Norm.Normalize()
					Norms[Index]=Norm.X()
					norms[Index+1]=Norm.Y()
					Norms[Index+2]=Norm.Z()
										
					CIndex:+1	
					Index:+3
				
				Wend

Rename the maths funcs to whichever you're using, all standard ops.

eizdealer

(Posted 2005) [#6]

Aah now I get it. The problem is that I used 3 independant vertices for each triangle. I think that this can be fixed easily.
So I suppose you should merge vertices with the same coordinates after loading the mesh (depends on how that mesh is saved of course).

Is there a way to do smoothing across non-shared vertices faster? Just being curious.

What stays is that debug issue.

fredborg

(Posted 2005) [#7]

Yes, build an array:

Type SharedVert
field x:float,y:float,z:float
field nx:float,ny:float,nz:float
EndType
local sharedverts:TList = New TList
local VertReference:SharedVert[VertexCount]
For Every Vertex
  local found = false
  for sv:SharedVert = EachIn SharedVerts
    if vertex position = sv position
      found = true
      exit
    endif
  next 
  if found = false
   sv:SharedVert = new SharedVert
   sv position = vertex position
   sharedverts.addlast sv
  endif
  VertReference[vertexnumber] = sv
Next
ClearList SharedVerts

And then use the VertReference[] instead of searching through all the vertices for each triangle.

Robert

(Posted 2005) [#8]

It might be a good idea to print some debug info from the code as well - just to make sure that loops are being executed the correct number of times, and to identify where slowdown is occuring.

eizdealer

(Posted 2005) [#9]

The number of executed loop iterations is correct (checked it like you suggested with print). The slowdown seems to come from the vast amount of iterations. It irritated me because I didn't know there are faster ways to do it.
What keeps irritating me is that debug thing. What's BRL's position on that?

fredborg

(Posted 2005) [#10]

eizdealer are you even reading the posts?

eizdealer

(Posted 2005) [#11]

I hope so...
I'm sorry if I missed something though.
I've got a fast working method now - thank you.

Edit:
Ah got it, I'm really sorry :(
This day was just too long.
I thought you refer to 'merging' with that 'yes'