KDTrees and blender gui synthetics

Remember kids, if you use a synthetic oil, it's not a good idea to switch back to regular.



As far as I understand it, "KDTrees" are simply a data structure that says:

def kdtree:
def node:
x,y,w,h
split
low_node *
high_node *
parent *
direction

And, each node occupies a region of space defined by a x,y,w,h box (or x,y,z) and "splits" that box into TWO boxes, along only one of the axes (either x or y). This way, you can more efficiently partition static objects into a scene; this is like all BSP / octree scene management techniques; However, updating a KD tree is rather expensive, it really is good for storing static scenes though as it requires a far lesser node density and can expand into any other volume as needed.

So, they're used in blender's GUI; I'm getting my mockup GUI system to work slowly, and here are many panels defined by glViewports with text in them. The text system is nothing more than a badass texture font I used some free program to generate with 2 px padding and as a alpha only texture, so the memory required for those letters is quite minimal; although fonts are not conducive to mipmapping, so you must manually provide other LOD fonts for your program. Don't forget that always mipmapping is better for your hardware.



I'm also perfecting my cMesh class, which will provide a full next generation mesh including armature animation and animux system, basically equaling and exceeding the capabilities of all existing high definition games; And doing so in a manner consistent with next gen technology (VBO/Shader) while still retaining the ability to be processed via older cards, at great CPU expense.

It looks something like this:



The concept is present in all games I have hacked, and works like this:

A mesh consists of "tiles", which are separate VA/IA's that contain some amount of triangle strips/triangles/quadstrips with a consistent vertex format and ideally contiguous data. This means each tile can store different vertex parameters, the usual culprits are:

current vertex position (3)
next vertex position + weight (4) //For mesh keyframes only
texcoord 0 (2) //1st texture coordinate
texcoord 1 (2) //2nd texture coordinate (if you have seperate UV mappings, not efficient)
normal (3) //Required for any lighting
binormal (3) //can be shader generated, but space may need to exist in VA array)
matrix indicies (4) //Required to skin a mesh that has more than 1 matrix deforming it
matrix weights (4) //Required to skin a mesh properly

So, each tile can behave as a independent mesh. Above a tile is a tile state, which contains the RC (RenderCommand) array for actually issuing the stripping indicies and material changes and matrix palette updates for this mesh.

Above that is the TileTree, so you can swap/zsort/prioritize and use lod tiles as needed.

the concept of a tile is to load all mesh data into your graphic card, and then merely tell the card what to use to render via a few array binding commands. This is extremely efficient, as it supports mesh instancing to a large degree, and prevents transferring data to the card. The only drawback is you still have to transmit matrix updates to the card, but even a 270 bone character (like Valgirt) this is still far less information that a small VA.

So, once you have tiles setup, we have a generic bone/matrix animation system, with a matrix class (yes, I like quat's too, but matrices require less conversions in a game setting; these matricies can be changed to be only state driven mind you.).

The heart of this system is the base animation classes, which consist of "Keys" which are blocks of static data to interpolate between, "Channels" which are a list of keys and times, and "Animations" which combine channels together to form complete animations.

The Animux is a animation multiplexer, which combines any number of animations together, so that you can use multiple types of animations together, for instance "Run_legs" and "Shoot_Torso" like Quake, or "Face_Phoneme_ma" and "Run". This allows you to make characters that can walk, talk, and run + shoot at the same time, and even use IK calculations as you want.

I've probably done this thrice before, but THIS time, I've got it nailed, and have massive amounts of evidence and experience with the new GLSL to support this type of design. Hopefully, I can get AniStar up and running so I can actually have a program that can make animations for given characters.

Z out.

Hacking Success; Dragon Quest Swords broken!

Add:

Godzilla: Unleashed
Rampage: Total Destruction
Dragon Quest Swords
Monster Hunter G
Monster Hunter Tri
Super Smash Bros. Brawl
Carnival Games *
Super Mario Galaxy
NiGHTS
ect...

to the list of games I can extract models from.

I wish I knew who to give credit to, but all I needed was this little function here to finally break apart the .fpk / Dragon Quest Swords compression format (I was really close too, ironically)


typedef unsigned int u32;
typedef unsigned short u16;
typedef unsigned char u8;


int endian=1;

u32 BE32(u32 data)
{
if(endian)
return ( (data<<24) | ((data<<8)&0x00ff0000) |
((data>>8)&0x0000ff00) | (data>>24) );
else
return data;
}

int blen;
int fbuf;

/* PRS get bit form lsb to msb, FPK get it form msb to lsb */
int get_bits(int n, char *sbuf, int *sptr)
{
int retv;

retv = 0;
while(n){
retv <<= 1;
if(blen==0){
fbuf = sbuf[*sptr];
//if(*sptr<256)
//{ printf("[%02x] ", fbuf&0xff); fflush(0); }
(*sptr)++;
blen = 8;
}

if(fbuf&0x80)
retv |= 1;

fbuf <<= 1;
blen --;
n --;
}

return retv;
}

int uncomp(char *dbuf, int dlen, char *sbuf, int slen)
{
int sptr;
int dptr;
int i, flag, len, pos;

blen = 0;

sptr = 0;
dptr = 0;
while(sptr < slen){
flag = get_bits(1, sbuf, &sptr);
if(flag==1){
//if(sptr<256)
//{ printf("%02x ", (u8)sbuf[sptr]); fflush(0); }
if(dptr < dlen)
dbuf[dptr++] = sbuf[sptr++];
}else{
flag = get_bits(1, sbuf, &sptr);
if(flag==0){
len = get_bits(2, sbuf, &sptr)+2;
pos = sbuf[sptr++]|0xffffff00;
}else{
pos = (sbuf[sptr++]<<8)|0xffff0000;
pos |= sbuf[sptr++]&0xff;
len = pos&0x07;
pos >>= 3;
if(len==0){
len = (sbuf[sptr++]&0xff)+1;
}else{
len += 2;
}
}
//if(sptr < 256)
//{ printf("< %08x(%08x): %08x %d> \n", dptr, dlen, pos, len); fflush(0); }
pos += dptr;
for(i=0; i< len; i++){
if(dptr < dlen)
dbuf[dptr++] = dbuf[pos++];
}
}
}

return dptr;
}



Thanks to that mess, I could use my own BRRESToOBM and the Pipeworks1.4ToOBM converters to completely extract the models and import them into blender.

Why do this, you ask?

Simple! Since NOT A SINGLE DAMN PERSON here is competent enough to help me, my only method of QA/QOS/QMS/verification is checking my work against commercial products. It's a very useful method as you often get to see techniques for animation, texturing and shading that are well known to industry but not well documented, or just plain hard to find.

Some of the cool things I've learned:

*Use additional bones inside of the arm joints on your characters; This allows you to retwist the arm visually while still keeping the IK chain unbroken. This is a classic character animation technique that I never had seen in practice.

*Use lots of matrices and bleed the weights out as much as possible, trying not to exceed 4 weights per vertex; Don't just use 0.5/0.5 blending factors (Valgirt has 272 bones...)

*If you are applying a bump/normal map to a character, use the I8A8 texture format and simply calculate the z component in the shader; This costs no additional instructions AND guarantees a normalized z component which you would have to do anyways.

*Use well painted textures, and don;t be afraid to use non-contiguous models (fins, talons, tongues, even neck/finger joints do not always have to be connected to the base mesh!

*Make sure you add in additional transform bones to characters, such as a Root Node and X/Y rotation nodes.

*for mesh modeling, targeting 3k verticies isn't really an issue.

*Always sort your meshes by: Material, Matrix Deformation Pool, Index array type.

*Always convert your final mesh pools into triangle strips if you can; Avoid quads and triangles. If you must use triangles, sort them in a indexed triangle list so that each next triangle shares adjacent verticies. Note that on file loading, you can always convert strips back to triangles; but not the other way around.

*Matrix deformation systems allow you to do things you could never do with bone animation systems; Since you just get a 3x4 float matrix per 'bone', you can apply translation, rotation, scale, and shear transformations. Since the hardware is unaffected by the values you put in those matrices (same number of ops) you're allowed to really have fun animating and be guaranteed consistent results anywhere.

*Mesh keyframes are A-OK and should be combined into your matrix mesh; for example facial poses and stuff. Simply apply those before running your mesh through the shader; You can get very awesome character animations this way.

*Try and avoid making your matricies match a 'skeleton' of you character; This often results in hard mechanical animation that looks not fun. It also makes your artists have to work harder, because a 'bone' does not behave like a matrix. Usually, with matrix deformations, you want the matrix to be at the 'ring center' of the mesh data, so that scaling and transforms will behave as you expect. Interestingly, since matrices have no constraints, you can always make this look like the hard mechanical, but you can't do that the other way around.

*Add additional target matricies; It only costs a small amount of CPU and gives your models flexibility for grapple animations, picking up objects, and easier cinematic animations

*I've seen 11,000 vertex models fully shaded on the Wii. No kidding. With 200 + bones. Think about that for a second. Think about how much more powerful your PC is than that.

*Most importantly, animate/design for fun. Don't make things realistic; It's a waste of your time because commercial studios can always do that better than you can. And who wants to play a realistic game anyways?

I'll post pics later, today I have more beer to acquire!

-Z

Super Smash Bros Brawl model format

So I have been exploring Brawl.

I've learned a little more about constructing armatured models, this is primarily useful for my art team in assisting their understanding of how professional projects handle their game media. Using references is extremely informative when you create your own models, as you get to learn from others mistakes more quickly, and see new ways to make special joints and features.

I'm doing this out of pure academic interest, as I found out there is not much difference between this and the melee formats. I hacked both, but brawl models in general look better.

So here's the Ridley Trophy in Blender, definitely not something desirable to wake up to:



And yeah, I still have that awesome little plastic Ridley figurine that Kelly let me have. He's quite happy guarding my desk!

Peace!

-Z