Hey look, a quadtree

So what's so special? This is a common data structure that everyone one of you should be able to do from memory. It's extremely simple, and uses recursion. Simply make a tree with each node linking to 4 child nodes that evenly divide space, and let each node store a list of pointers or the data itself.

The special part, is this is a generic quadtree, so, instead of 'storing' objects, it stores XData::Quadtree::Proxy object POINTERS to a XData::List, which means that Proxy lifecycle is left to the user (working on making it pointeriffic and more auto-delete) but that also means that every node stores a list of those proxy pointers, so that your game object:

class MyGameObject : public Game::BaseObject {
private:
XData::Quadtree::Proxy m_proxy;
}

Can simply access the quadtree as such:

qtree.insert( obj.m_proxy );
qtree.remove( obj.m_proxy );
m_proxy.IsValid();
qtree.get( XData::Array &, fptr_to_Collision_Function, collision_function_data );

So what this means, is in the above picture you can draw arbitrary edges for a odin-sphere style level, which get their proxies put into the quadtree. This is dangerous only if you forget to remove the proxy before deleting the object. But it means that you can query arbitrary shapes against the quadtree and get a quick enough broadphase test for intersection. Insertion is always better than O(log(n)), deletion/update is best case O(1), worst case O(log(n) + 1). Access is linked list, so fast iteration is possible.

Quadtree's are good for dynamic data, that is if everything is changing quickly. There are other methods for static data that are far superior, like KDTrees or Spaceblocks or even AxisSweeps, but quadtrees are a general good purpose solution that's still good in performance to be viable for many applications. In fact, you probably won't need much more than this, unless you have severe restrictions that force you to use sorted space blocks.

If you are making a 2D game, please do not use tiles. I will hate you, and you should be competent enough to make a quadtree (think Game Maker) that can handle arbitrary shapes and so forth.

Go look at this game to see one of these methods in action

-Z

SSE Optimizations

So I got "My First SSE Optimized Quaternion Rotation Function" today...Note that I have to use GCC asm, which is a bitch compared to other forms, however, it has huge advantages, so just deal with it you pansys.

The point is, the way VMath works is by:

extern void (*SomeFunc)( Vec4 & ); //In the VMath.h, declare this pointer to be extern so it is not duplicated every time you include igtl_vmath.h

And then, in the VMath.cpp:

void (*SomeFunc)( Vec4 & ); //Function pointer for routine declared ONLY in cpp

And then, we call Initialize(), which reads your cpuid and sets function pointers to appropriate locations, so that if you have SSE, it can use it on runtime, and if not, it won't. Unfortunately, the calling overhead is the same.

Also, your project settings need the -mmmx and -msse flags to tell GCC to use SSE.

This is problem 3/4, I need to reduce the call syntax overhead, but I do not believe this is possible without using some strange compiler __attribute__ or __fastcall for you MS folks. This will be an experiment to run.

Actually, I do not know of a better mechanism to use; If I need to detect processor type on runtime and switch functions, then I do not see any better way than using a function pointer. Although, this should be fast enough; SSE optimizations do not become apparent in small frame sense. In fact, you will see little gain for most functions, where they shine is parallelism. For example, if all your Game::Object's have a quaternion, then you probably 'update' each one of them independantly, which requires moving a lot of pointers and so on. Instead, if you make a batch_updater() function, then you can pass a pointer to your array of game objects, and store the values used commonly for all those transformations in registers, and thereby signifigantly speed up your application by removing redundant load calls and such...

More on this as it progresses; The nice part, is since VMath already works, I don't have to f*** with the SSE part until later, because it was DESIGNED RIGHT! That means I can hand that coding task to any other programmer and let them optomize it to hell while I continue building more components into the framework. Hence my title as Developer.

Peace ya'll!

-Z

Thumbs Up!

Okay, I got it. Matrix Palette exporter works fine now.


Next up is adding in textures in MIF/QIF format (already done, copy paste job), and then deciding the structure for spread-optimized armature/matrix palette, and then keyframes using vertex duplicate's.

Of course, now that THIS works, it'll be time to shove it onto the iPhone. Imagine that, "Monster Game" for the iPhone! Course it'll be stripped down, but hey, sounds fun.

Peace ya'll!

-Z

Well, goddamnit, GODDAMNIT! Again, again!

Well, still can't get it right. The materials have been fixed, apparently, but only for some models. Others still have trouble??? (Saurosaur model has some trouble when it's subsurfaced, but I believe this is related to the matrix problem at hand)

At least this picture is a little less boring


Also, I have a feeling some people don't know what spinal curves are. Actually, if you have studied animation, you might understand these as "Action Lines" or "Line of Action" or whatever name you want to give them. In fact, if you build your skeleton correctly, you can draw these spinal curves, and it shows you the model's action pose, from which it is WAY easier to tweak that action line than it is to screw with posing bones. I hope that Blender integrates this posing system into it's bones, it would only require an additional flag and some simple bone-blending editing tricks. It's very helpful for bringing things to life. What good is this realtime though? It's helpful if you don't have shaders on your PC, so you can at least see the game sort of. It's also helpful for special effects, and some other 'interesting' deformations... he he.



I still need help with the exporter. It's not to my QC standards yet.

-Z

Well, goddamnit again!

Still fighting. Hang in there, plastic lizard monster!

And yes, you will be fighting against this mo'fo, but as you can see, there are still glitches in the code. I am still lost as to where, it seems that larger models export better (how crazy is that?!) and they work fantastically well, as you can see.

What is wrong:
Materials are not perfect, there are 1 spots on this model that have incorrect materials
Not all deformation groups are correct, you can see the spike present. On lower res models, it's way uglier.

I need help.

-Z

Well, goddamnit!

Well. I still am having a hell of a time getting my GRF exporter to cooperate.

For some reason, it works fine for models with less than 24 bones. However, models that have more than that (all of mine do) it screws up something with the vertex data, or maybe the bones, because suddenly, and irrationally, the bone groups dissociate and the neck will move when you bend the tail.

I'm at a loss here, as I've checked the algorithms a hundred times, checked and verified the DATA ITSELF, so that I know that the bones are correct, faces, everything is correct... checked the C++ code, which reads it EXACTLY as the file, so I know the C code works since it is general case... so, where is the error?

My guess is it lies inside of python somewhere.

Maybe a stupid screenshot will cheer me up:

Whoopee... old school poser models. yay.

Also, I have the fragment program and vertex program working fine. Tested, verified, fun to play with and easy to work with. I'll be much happier when I can GLSL this mess, although these programs are just about as fast as it can get, so not much reason to yet.

Blender is cooperating fine, I've had no problems from it, aside from this list of annoyances:
1. No bone weight keyframes available, I need to be able to save weights in vertex groups as a keyframe
2. No UV keyframes available, I need to be able to save UV layer keyframes
3. Actions are not tied to anything, and they are still difficult to use for making a movie, most people just use the 'one large action' to do it. Make actions work like actions, not scene animations. Make the NLA mean something, dammit.
4. No support for mesh keyframe animations that makes sense. Why can't I just IPO a list of keyframes, instead of making 1 ipo for each keyframe (which is hell without a script, by the way)
5. More materials. I need more than 16 materials. try 127? or 255?
6. Much improved curve support. I should be able to hook curve verticies ONTO anything, like armatures and objects and verticies, without having to use the vertex hook <-> empty <-> curve thing.

and so on.

Hopefully I can get this $@#*( problem solved. This isn't a specialized problem, it's general, so it works for any matrix-palette system, including the coveted iPhone, PS3, and the PC.

Peace folks,

-Z