Spring RTS Engine

Posted: **01 Aug 2008, 02:34**

Seeing as some people
http://spring.clan-sy.com/phpbb/viewtop ... 7&start=20

seem to be quietly working on new animation/model systems, I felt like trying someting too and wanted to make a LUA script for .md5. I have so far managed to draw the contents of an .md5mesh in a basic way (no normals, etc). Unfortunately however, the performance so far really sucks.

This is some crappy .md5 model I found on the internet with apparantly 4372 triangles. This would be the equivalent of about 20 guys with a more reasonable 200polygons for example. Sadly this makes fps go down to around 18. Looking closely at the model, it's really bad, it doesn't even make use of skeletal animation the way it's setup, with one mesh per bone. I couldn't find any of the doom3 models around, might install it to get at them later.

It's probably handling all the weights that slows it down the most, requireing a quaternion rotation (25 multiplications + 25 additions) and all the function calls between the thousands of weights, vertices etc.

I was hoping to maybe unload processing into the vertice shader to circumvent LUA:s disadvantages, but I think one would need to use a geametry shader (nvidia8800+) for this to be feasible. In the end it's probably necessary to go with engine side code to be practical, but I have never felt like going trough with the troubles of setting up the ability to compile the spring source code and then getting intimate enough to work with it.

Anyway it's still useful to me as an experiment to learn stuff, see what can be done etc so I will probably continue a bit more.

Here's the code sofar:

Code: Select all

function widget:GetInfo()
  return {
    name      = "boneanim",
    desc      = "Skeletal animation",
    author    = "zpock",
    date      = "July 28, 2008",
    license   = "GPL",
    layer     = 0,
    enabled   = true  --  loaded by default?
  }
end

local shieldshader
local joints = {}
local meshes = {}

function widget:Initialize()

    io.input("cubby3.md5mesh")
	local total = io.read("*all")
	
	_,_,skel = string.find(total, "joints %{(.-)%}")
	
	local i ,j, t = 0, 0, -1 
	while true do
		i, j, nr = string.find(skel, '(".-".-)\n', j+1)
		if i == nil then break end
		
		t = t+1
		local _,_,name = string.find(nr, '"(.-)"')
		local _,_,parent = string.find(nr, '".-" (.-) ')
		local _,_,x = string.find(nr, '%( (.-) ')
		local _,_,y = string.find(nr, '%( .- (.-) ')
		local _,_,z = string.find(nr, '%( .- .- (.-) ')
		local _,_,xo = string.find(nr, '%(.-%) %( (.-) ')
		local _,_,yo = string.find(nr, '%(.-%) %( .- (.-) ')
		local _,_,zo = string.find(nr, '%(.-%) %( .- .- (.-) ')
		
		local joint = {}
		joint.name = name
		joint.parent = tonumber(parent)
		joint.x = tonumber(x)
		joint.y = tonumber(y)
		joint.z = tonumber(z)
		joint.xo = tonumber(xo)
		joint.yo = tonumber(yo)
		joint.zo = tonumber(zo)
		
		local kuk = 1 - xo^2 - yo^2 - zo^2
		if kuk < 0 then
			joint.wo = 0
		else
			joint.wo = -math.sqrt(kuk)
		end
		
		joints[t] = joint	
 	end
	 
	local i2, j2, t2 = 0,0,0
	while true do
		i2,j2,s = string.find(total, "mesh %{(.-)%}", j2+1)
		if i2 == nil then break end
		
		local verts = {}
		local tris = {}
		local weights = {}
		
	
	
	i ,j = 0, 0
	while true do
		i, j, nr = string.find(s, "vert (.-)\n", i+1)
		if i == nil then break end
		
		local _,_,t = string.find(nr, "(%d+)")
		local _,_,u = string.find(nr, "%( (.-) ")
		local _,_,v = string.find(nr, "%( .- (.-) ")
		local _,_,start = string.find(nr, "%) (%d+)")
		local _,_,count = string.find(nr, "%) %d+ (%d+)")
		
		local vert = {}
		vert.u = tonumber(u)
		vert.v = tonumber(v)
		vert.start = tonumber(start)
		vert.count = tonumber(count)
		
		verts[tonumber(t)] = vert
		
 	end
	 
	i ,j = 0, 0
	while true do
		i, j, nr = string.find(s, "tri (.-)\n", i+1)
		if i == nil then break end
		
		local _,_,t = string.find(nr, "(%d+)")
		local _,_,v1 = string.find(nr, "%d+ (%d+)")
		local _,_,v2 = string.find(nr, "%d+ %d+ (%d+)")
		local _,_,v3 = string.find(nr, "%d+ %d+ %d+ (%d+)")
		
		local tri = {}
		tri[1] = tonumber(v1)
		tri[2] = tonumber(v2)
		tri[3] = tonumber(v3)
		
		tris[tonumber(t)] = tri	
 	end
	
	i ,j = 0, 0 
	while true do
		i, j, nr = string.find(s, "weight (.-)\n", i+1)
		if i == nil then break end
		
		local _,_,t = string.find(nr, "(%d+)")
		local _,_,joint = string.find(nr, "%d+ (%d+)")
		local _,_,bias = string.find(nr, "%d+ %d+ (.-) ")
		local _,_,x = string.find(nr, "%( (.-) ")
		local _,_,y = string.find(nr, "%( .- (.-) ")
		local _,_,z = string.find(nr, "%( .- .- (.-) ")
		
		local weight = {}
		weight.joint = tonumber(joint)
		weight.bias = tonumber(bias)
		weight.x = tonumber(x)
		weight.y = tonumber(y)
		weight.z = tonumber(z)
		
		weights[tonumber(t)] = weight	
 	end
	
	meshes[t2] = {} 
	meshes[t2].verts = verts
	meshes[t2].tris = tris
	meshes[t2].weights = weights
	
	t2 = t2+1 
	 
	end  
end

function widget:GameFrame(n)
	
end

function qmult(qax,qay,qaz,qaw,qbx,qby,qbz,qbw)
	local rw = (qaw * qbw) - (qax * qbx) - (qay * qby) - (qaz * qbz)
	local rx = (qax * qbw) + (qaw * qbx) + (qay * qbz) - (qaz * qby)
	local ry = (qay * qbw) + (qaw * qby) + (qaz * qbx) - (qax * qbz)
	local rz = (qaz * qbw) + (qaw * qbz) + (qax * qby) - (qay * qbx)
	return rx, ry, rz, rw
end

function qrot(qax,qay,qaz,qaw,qbx,qby,qbz,qbw)
	rx, ry, rz, rw = qmult(qax,qay,qaz,qaw,qbx,qby,qbz,qbw)
	rx, ry, rz, rw = qmult(rx,ry,rz,rw,-qax,-qay,-qaz,qaw)
	return rx, ry, rz
end

function widget:DrawWorld()
	local numtris = 0

	for key2, value2 in pairs(meshes) do

	for key, value in pairs(value2.weights) do
		
		value.xp, value.yp, value.zp = qrot(joints[value.joint].xo, joints[value.joint].yo, joints[value.joint].zo, joints[value.joint].wo, value.x, value.y, value.z, 0)
	
		value.xp = value.xp + joints[value.joint].x
		value.yp = value.yp + joints[value.joint].y
		value.zp = value.zp + joints[value.joint].z	
	end
	
	for key, value in pairs(value2.verts) do
		value.xp,value.yp,value.zp = 0,0,0
	
		for i = 0, value.count - 1 do
			local bias = value2.weights[value.start + i].bias
			value.xp = value.xp + value2.weights[value.start + i].xp*bias
			value.yp = value.yp + value2.weights[value.start + i].yp*bias
			value.zp = value.zp + value2.weights[value.start + i].zp*bias
		end		
	end
	
	gl.DepthTest(true)
  	gl.DepthMask(true)

    gl.PushMatrix()
  	gl.Translate(100, 100, 100)
  	
	gl.Texture('mupp/pCube1_joint1 copy.jpg')
	
	for key, value in pairs(value2.tris) do
		gl.BeginEnd(GL.TRIANGLES, function()
    	gl.TexCoord(0,0)
		gl.Vertex(value2.verts[value[1]].xp,value2.verts[value[1]].yp,value2.verts[value[1]].zp)
	   	gl.TexCoord(1,0)
		gl.Vertex(value2.verts[value[2]].xp,value2.verts[value[2]].yp,value2.verts[value[2]].zp)
	   	gl.TexCoord(1,1)
		gl.Vertex(value2.verts[value[3]].xp,value2.verts[value[3]].yp,value2.verts[value[3]].zp)
		end)
		numtris = numtris + 1			
	end
  		
  	gl.PopMatrix();
  	end
  	
  	Spring.Echo(numtris)
	
end

Posted: **01 Aug 2008, 03:38**

I really wish you guys would all communicate and work together rather then have three seperate projects. Together you all probably form the best in coding for Spring, and this is something most modders are drooling over. A unified attempt would result in getting skeletal animation far sooner...

Posted: **01 Aug 2008, 06:27**

I want to note, for the record, that I think that the very best way to go about this would be to build mesh interpolation code (vertex --> vertex) so that you're no longer using the bones or weights, and store each motion cycle in a way that can be called by Lua.

Yeah, yeah, I know, that means no perfect interpolation between states that aren't accounted for... so what? Players will not notice it very often, it's not like a FPS, and if there's a way to request the current state vis frames-since-start of a given sequence of X length, Y frames in, for example, then tweens could be made for handing certain things off (going from running state to walking and firing, for example).

Also, most IK systems in games have had a terrible problem- timing is fixed. I'd really like to see a system where, based on the positions of the IK bones, etc. during arbitrary frames... were interpolated to any arbitrary number of gameframes, based on what the game designer wants. That way, if you need to change the speed at which a character "reloads", for example, you'd just change a number, and voila, problem solved. Much nicer than requiring people to go back to their 3Dsoftware, re-edit that animation all over again, and export it, all over again. That should be trivial, but I wanted to stick it in as a feature request, here... it'd be a real shame if we got this, and it was fast, but was so inflexible that few people wanted to use it.

I really don't think that there's much of a practical use for a full IK system, however. I think we're just going to find it's too damn slow. Fetching a bunch of relative vertex positions is a lot faster than doing the calcs needed to displace them on the fly, shader or not, I suspect.

Lastly, whatever's done ultimately is going to have to intersect with COB and traditional BOS animation in some useful way, to really be workable. DoW has both IK animation (although I'm pretty sure they just used static frames, like I'm talking about here) and procedural animation, for turrets. A system that combined the power of BOS for dealing with very specific events, and an IK system that ran really fast would be the best of all possible worlds, imo.

Posted: **01 Aug 2008, 07:52**

My main desire is primarily the ability to craft animations succesfully in a 3D package, rather then the very frustrating current method.

Beyond that, being able to do non socketed joints for organic objects would make a lot of things a lot more believable.

Posted: **01 Aug 2008, 08:59**

Argh wrote:I want to note, for the record, that I think that the very best way to go about this would be to build mesh interpolation code (vertex --> vertex) so that you're no longer using the bones or weights, and store each motion cycle in a way that can be called by Lua.

You realize that's SLOWER, right?

Posted: **01 Aug 2008, 09:29**

Interpolation is done at the bone level. I think the main problem with my script could be memory acess, since I used tables and those are probably ages slower then c arrays.

Posted: **01 Aug 2008, 09:59**

Ways to increase the lua performance
(w/o using a shader or using DLists etc.)

first your initialization is slow/unoptimized:

Zpock wrote:

Code: Select all

function widget:Initialize()
           ...
	_,_,skel = string.find(total, "joints %{(.-)%}")
           ...
end

localize "skel" and use total:find("joints %{(.-)%}")
also you shouldn't ^2 and you should localize math.sqrt, also you forgot to call io.close()

Zpock wrote:

Code: Select all

function qmult(qax,qay,qaz,qaw,qbx,qby,qbz,qbw)
	local rw = (qaw * qbw) - (qax * qbx) - (qay * qby) - (qaz * qbz)
	local rx = (qax * qbw) + (qaw * qbx) + (qay * qbz) - (qaz * qby)
	local ry = (qay * qbw) + (qaw * qby) + (qaz * qbx) - (qax * qbz)
	local rz = (qaz * qbw) + (qaw * qbz) + (qax * qby) - (qay * qbx)
	return rx, ry, rz, rw
end

function qrot(qax,qay,qaz,qaw,qbx,qby,qbz,qbw)
	rx, ry, rz, rw = qmult(qax,qay,qaz,qaw,qbx,qby,qbz,qbw)
	rx, ry, rz, rw = qmult(rx,ry,rz,rw,-qax,-qay,-qaz,qaw)
	return rx, ry, rz
end

1. localize those functions
2. "rx, ry, rz, rw = qmult(rx,ry,rz,rw,-qax,-qay,-qaz,qaw); return rx, ry, rz" you don't use the returned rw here, so don't compute it

Zpock wrote:
Code: Select all
	for ... in pairs(..) do.. end

don't use pairs or ipairs, they are slow, just use: for i=1,#array do local v = array; .. end

Zpock wrote:

Code: Select all

		value.xp, value.yp, value.zp = qrot(joints[value.joint].xo, joints[value.joint].yo, joints[value.joint].zo, joints[value.joint].wo, value.x, value.y, value.z, 0)

assign "local joint = joints[value.joint]" only once and reuse it

Zpock wrote:

Code: Select all

	for key, value in pairs(value2.tris) do
		gl.BeginEnd(GL.TRIANGLES, function()
    	gl.TexCoord(0,0)
		gl.Vertex(value2.verts[value[1]].xp,value2.verts[value[1]].yp,value2.verts[value[1]].zp)
	   	gl.TexCoord(1,0)
		gl.Vertex(value2.verts[value[2]].xp,value2.verts[value[2]].yp,value2.verts[value[2]].zp)
	   	gl.TexCoord(1,1)
		gl.Vertex(value2.verts[value[3]].xp,value2.verts[value[3]].yp,value2.verts[value[3]].zp)
		end)
		numtris = numtris + 1			
	end

1. don't ever use gl.BeginEnd(PrimitiveType,function() ... end) in performance critical code! just define the function somewhere else and use glBeginEnd(PrimitiveType,myDrawFunction,arg1,arg2,arg3,...)
2. don't run glBeginEnd in the for-loop, instead put the for-loop in the glBeginEnd!

PS: there I wrote once a widget to compare all those optimizations. The numbers are in the ca wiki and the widget+code in ca-sandbox

Posted: **01 Aug 2008, 11:46**

Thank you for taking time with these suggestions Jk, i'll try to implement them and see if performance improves. I'm also going to try using the vertice shader for some work, I think it's possible. Maybe it can be made efficient enough for a single unit per player like a jedi in IW. I'm also considering if one model could be cloned for animating large squads of identical guys.

Also if someone could send me a better md5 file to test with that would be much appreciated.

Posted: **01 Aug 2008, 14:19**

Since the cat is out of the bag now, might as well deliver an update
of my own:

Fatties01.jpg: (161.49 KiB) Downloaded 137 times

Fatties02.jpg: (157.19 KiB) Downloaded 111 times

The shader does normal- and parallax-mapping, although the latter
effect is not so strong with the models I've imported so far. I've also
looked into doing the mesh-skinning in a shader, but MD5 isn't really
designed for it (the data layout makes it GPU-unfriendly). IIRC Quake
(4) actually converts its models to a different format (MD5R?) to deal
with the speed issue, which would certainly have to be done in Spring
as well (RTS ==> many units). On the upside, MD5 models can come
with multiple instances of the same submesh (a submesh is somewhat
analogous to a piece in S3DO models) which they can choose to show
or hide, allowing for primitive LOD reduction (hide the high-detail mesh,
show the lowres one). Another advantage is the possibility to bind any
number of material sets you wish to a submesh (enabling easy-as-pie
multitexturing, with the one drawback that submeshes are not shared
across models), I've already written a swapping system. Next up on my
list is animation blending; right now it can only play one anim at a time
(and transitions between them are instantaneous).

Of course, the truly hard part of all of this is integrating it properly into
Spring, which doesn't have much abstraction in place for handling the
different model formats. Adding support for a third (with its own unique
animation control requirements, COB isn't really usable here) is a MUCH
larger undertaking than getting to this point was. IF I decide to wrap up
the work, it'll first be preceded by rather noticeable engine changes.

Argh wrote: I really don't think that there's much of a practical use for a full IK system

I really don't think you know what the MD5 format is about.

(It doesn't
provide info on joint constraints, so IK isn't even possible out of the box.)

Posted: **01 Aug 2008, 15:54**

Who said there'd be only one jedi per player in IW? >_>

Can't rest until I see jedi commanders leading forces into battle:

Posted: **01 Aug 2008, 16:41**

Well only 2 sith at a time, and the jedis are pretty much extinct? It's just an example of where 1 unit could make sense, another would be a single giant monster on the map.

It should be possible to do .md5 style skinning on the GPU, you just have to put some limits on the number of weights per vertex, bones etc which would make sense anyway? As spring is CPU bottlenecked it would make sense to either use the gpu, or try to put the skinning on a separate thread(s)...

One reason to do it on the CPU would be to clone the animations on multiple units so you could have say 100guys in a square formation doing the same thing.

Anyway it's a good idea to try different methods and see what might work best, perhaps using something more primitive like md3 which I think works kind of like what argh describes might be better, or to ignore the weight positions in md5 and instead use bind-pose vertice locations which can be calculated from the md5, which is useful since it seems reasonably well supported by exporters.

As for integration I think it's about time to rehaul the whole way units work anyway, ditch the old TA stuff but keep it working the same it does now separatly for bwc. But for starters why not just hide the old model, render the md5 in it's place and control its animations via LUA but keep the unit functioning as usual.

Posted: **01 Aug 2008, 17:19**

@KDR:

No, you're wrong. Moving a mesh vertex around has got to be slower than fetching that mesh vertex from an array, hands down. To move it the takes quite a lot of math to do the interpolation step. I'm saying, do that at runtime, get it over with, and then pay a lower cost later. A pre-built display list is very fast, and that's what I'm talking about- large numbers of display lists, just sitting there in memory, waiting to be shown like movie cels.

There is no good reason I can think of to do real interpolation between mesh verts. Almost all uses of this are going to be pattern / cyclic animation cycles like they are in BOS, but with a stronger emphasis on "pattern", ala the totally identical animations in DoW, where everything was the same every time.

I just had a crazy thought, though. What if this worked by doing an interpolation between two .S3Os with identical numbers of vertices? Then we'd just need a timer. No huge problems with bones and other issues- they could be left to modelers to handle, outside the box, and would mean no huge new engine code would be needed, as well. Just a thought...

Posted: **01 Aug 2008, 19:54**

I got it working using the shader instead of CPU, and now I got NO noticable framedrop at all!, I'll try and implement further functionaliy, that is animation and textures/mapping, and see what happens.

Posted: **01 Aug 2008, 20:20**

great!

Posted: **01 Aug 2008, 21:58**

Argh wrote:No, you're wrong. Moving a mesh vertex around has got to be slower than fetching that mesh vertex from an array, hands down.

Er, what? How do you move a vertex without fetching it?

Do you realize how fast the memory demand grows for animations with vertex interpolation? Some Quake 3 playermodels went to over 20MB just for the mesh and animations. Stuffing all that into display lists (which duplicate a lot of data) will increase the load even more. Plus interpolation requires, well, interpolation which has to be done each frame since you have to blend two keyframes together. For our purposes vertex animation would suck because we need controller structures to aim guns and stuff, VA allows only intra-piece animation but you'd still have to segment the mesh to do anything not included in the anim, with SKA you can adjust any joint in your aiming code and stuff.

I'm not sure WHY the speed differs but I know it does because some consoles cannot do vertex animation but can handle skeletal animation. I suppose it has to do with SKA data being easier to send to the video system.

Posted: **02 Aug 2008, 00:51**

Really excited by developments here.

For the record, though we're set after the RotJ period, we will be allowing both sides to field larger amounts of knights and sith (though perhaps only one sith lord and a few masters). This is because we've taken the view that awesome > storyline fluff

I'll stop derailing though, I really want to see the skeletal animation go somewhere.

Posted: **02 Aug 2008, 04:44**

Wait a minute, so Kloot is doing this engine-side, while Zpock is doing this with lua?

Why?

Posted: **02 Aug 2008, 12:45**

It's a nice experience to have done an .md5 program, many people have written for example model viewers with no practical use at all.

Posted: **02 Aug 2008, 12:54**

You sure you wouldn't rather use your epic lua leetness to write a dropship script for us >_>

Posted: **02 Aug 2008, 19:59**

I have changed to using the "standard GPU method" of skinning instead of the previous "doom3 md5 style". This drastically cuts down on sending stuff over to the GPU at the cost of needing one additional rotation per joint. It seems to improve performance alot sofar, and I get maybe around a 200 to 180 FPS drop rendering one of these, a slightly better model I found:

I did normal mapping (seen on right one), altough I'm not sure if it's working correctly, it's kind of hard to tell (even with a flat gray colormap), but it does make a difference at least.

Spring RTS Engine

LUA MD5 (skeletal animation etc)

LUA MD5 (skeletal animation etc)

Re: LUA MD5 (skeletal animation etc)

Re: LUA MD5 (skeletal animation etc)

Re: LUA MD5 (skeletal animation etc)

Re: LUA MD5 (skeletal animation etc)

Re: LUA MD5 (skeletal animation etc)

Re: LUA MD5 (skeletal animation etc)

Re: LUA MD5 (skeletal animation etc)

Re: LUA MD5 (skeletal animation etc)

Re: LUA MD5 (skeletal animation etc)

Re: LUA MD5 (skeletal animation etc)

Re: LUA MD5 (skeletal animation etc)

Re: LUA MD5 (skeletal animation etc)

Re: LUA MD5 (skeletal animation etc)

Re: LUA MD5 (skeletal animation etc)

Re: LUA MD5 (skeletal animation etc)

Re: LUA MD5 (skeletal animation etc)

Re: LUA MD5 (skeletal animation etc)

Re: LUA MD5 (skeletal animation etc)

Re: LUA MD5 (skeletal animation etc)