Khayyam

Shinya - the game

2012-02-13T01:55:00.000+02:00

I have made too big progress with Shinya to not share it at last...

It uses the same rendering engine as Khayyam (Sehle library). Most new (and unreleased) features in Khayyam are actually implemented so it can be used as scene builder for Shinya. Among other things there are now reflections, occlusion queries, volumetric lights and darkness, instanced vegetation, layered terrain and so on...
No - I have not forgotten the new Khayyam release. The main problem holding me back is that there should be at least preliminary support for new materials for POVRay exporter. And things just progress too fast...

Shinya playable tech-demo is nearly complete. The biggest roadblock at moment is fixing remaining shader bugs for ATI GPU-s (this is the unfortunate consequence of writing engine in OpenGL...)

OK, I know - pics or it did not happen...

Sara looking down to Shinya world

Shinya will be adventure game, similar in style to Quest for Glory series. It takes place in (alternate and fictional) medieval times somewhere in central Europe.

There is a bit more vegetation in some areas

The main heroine is Sara - a bit complicated 12 years old girl, who is recently moved to the area with her aunt (she is orphan, as expected).

Another human being!

She will involuntarily dragged into some intrigues, conflicts and mysteries that have lately developed in this otherwise tranquil place. Or maybe not so involuntarily - se is, after all, a bit complicated damsel...

A mill at the main river

Modeling in Blender has been the other big time-consumer other than programming. I am slowly starting to get a grasp of this program - not a pro yet, of course.
The most complex model so far is cathedral - LOD 0 is about 190 000 triangles (LOD 1 about 2500). I develop Shinya mostly on laptop with NVidia GT540M GPU - and thus hope, that for the time it will be released it runs smoothy on most desktop computers at least.

Inside cathedral

The world of Shinya is 4x4 km freely roamable terrain. It has continuous day/night cycles - but you cannot stay awake indefinitely, even by using stamina potions. Thus NPC-s will have certain time to arrange things without player peeking over their shoulders.

Ah, almost forgot - Shinya it is written 深夜

Have fun!

Models and textures

2012-01-17T01:22:00.000+02:00

I have been busy with modeling and texturing for Shinya - and rewriting parts of Khayyam/Sehle to support certain must-be features like vegetation instancing and geometry LODs. Some (semi)finished things are available for download - more will come. Although certain parts will probably remain secret fro now...

Models

Sara the tween girl (Blender render)

Textured and rigged, about 6000 polygons. Blender source file and some exported formats can be downloaded from TurboSquid.

Oak tree (Blender render)

Oak tree with 3 LOD levels.

LOD0: 4407 vertices, 2791 faces
LOD1: 645 vertices, 442 faces
LOD2: 21 vertices, 7 faces
Collision (only trunk): 24 vertices, 16 faces

Blender source file can be downloaded from OpenGameArt.

Unfinished medieval house. About 10000 polygons, needs some agressive LODing.

Cathedral interior (Blender render)

Unfinished cathedral. About 55000 polygons - half of those are window frames. Needs also some agressive LODing to be usable in game.

Textures

Seamless ground texture - dead leaves

Small collection of plant and ground textures is available from my DeviantArt page.

Cut-out plants

A collection of cut-out plants at OpenGameArt.

Have fun!

Matching image colors with Texturewerke

2011-12-17T19:42:00.000+02:00

In the last post I demonstrated how to use TextureWerke for masked polynome high-pass filtering. In addition to that, TextureWerke 0.1 has another feature - matching colors between two (masked) images.

Workflow

Let's start with two images of stone wall we want to merge into one texture:

First image - a plain wall

Second image - a corner made of bricks

As you can see (among other things) the images have a bit different colors - the first one has more contrast and red. The bright background of the second picture influenced camera color adjustment logic so that the wall is more gray and has less contrast.
We will correct this automatically. First we move both photos to the same image (not necessary, but easier to compare) and add masks. We mask out all details that we do not want to influence final color - i.e. roof, shaded areas, brick structures, grass and background.

Masked images on top to each other.

Next we select the masked layer whose colors we want to change (Layer 2), invoke TextureWerke and choose color matching mode.

TextureWerke dialog window in color mode

Template is the (masked) layer whose color profile we want to emulate in selected layer.
Blurring reduces the noisiness of distribution curves and thus helps to overcome artefacts resulting from different sharpness of images. On the other hand it may mask out certain differences in color distribution and thus reduce the matching quality. You can always try and use what gives the best results.
And at last we apply the filter.

Image with adjusted colors

As you can see, the overall color and contrast of the (stone part of) wall matches with template image. On the other hand the areas that were masked out (bricks, backround...) are now completely off. But probably we did not want to use these anyways - except bricks maybe - but these can easily be copied and pasted from the original, and adjusted separately.

FYI: Internally the algorithm works by comparing pairwise the cumulative distributions of each image channel (R,G,B,A) and building a transfer function that translates the values with one distribution to the values with another (template) distribution.

And that's all. Have fun!

Texturewerke 0.1

2011-12-08T01:07:00.001+02:00

While doing textures for Shinya (the game with Khayyam/Sehle engine) I got frustrated with GIMP built-in tools and plug-ins available for texturing and decided to write my own tool Texturewerke. The initial version is now available for download from SourceForge:

Tarball and win32 precompiled binary

At moment it can do two things:

Adjust the colors of one (masked) image so it matches as well as possible with another. Thus you do not have to manually adjust color curves to merge several photographs into the same texture.
Filter out low frequencies from image (while keeping the average intact). This can be used both for the creation of seamless textures and for removing shade gradient from uniform surfaces (like walls, doors, whiteboards...) Highpass filter supports masking (in polynome mode), so you can mask out those details whose contribution you want to ignore (like pictures on wall).

Below is one possible usage scenario of Texturewerke highpass filter.

Polynomic highpass filter with masking

We want to use the following image as a texture. Unfortunately the background color is non-uniform and adjusting it by hand is boring work

The original image - notice the non-uniform shading of the wall

We select the are that we want to have uniform color (the wall). It does not have to be precise - the filter samples few thousand points from target area and thus small regions of wrong color do not disturb the result much.
In given case I used magic want to select white and then added and subtracted few rectangles.

Target region selected

Now we turn target region into mask, bu choosing "Add Layer Mask" from Layer menu.

Target region turned into mask

Next we invoke Texturewerke plugin and select "Lowpass" filter and "Polynome" mode.

The Texturewerke dialog window

It blurs image (internally) before calculating polynome approximation. The optimal size of kernel depends on image and the number of samples used. As general rule - the more samples it uses, the smaller can be the kernel.
Next we apply filter.

Masked image after applying polynome filter

As you can see, the unmasked area has almost uniform color/bightness now.
As the last thing, we delete (or turn off layer mask).

The final image - wall color is now uniform

And the final image has now nice uniform wall color.

There are few things to notice:

Polynome mode tries to approximate the average color of the image by two-dimensional polynome (up to 4th degree). The approximation process guarantees the correct behavior of the polynome only inside target region - the higher is its degree the faster it goes "wild" outside. Thus if you mask out some edges of the image the results probably will not look nice for anything above quadratic (2th order).
The unmasked area has to be at least 10% of original image
Samples are drawn randomly from unmasked area.
There is another highpass filter mode "blur", that subtracts blurred (lowpass) version of the same image. It does not support masking - but it may be more useful for the generation of highly uniform images (like grass and sand textures).

Have fun!

Reflective water with GLSL, Part II

2011-10-04T21:42:00.000+03:00

In the first part I explained how to implement a basic reflective surface. But as we could see, it was very poor approximation of true water, looking more like mirror lying on the ground. First because real water is almost never completely still. But it is also not perfect mirror - depending on viewing angle we can see more or less into the water.
Before going to implementing ripples I'll show how to adjust water shaders so the angle-dependency of reflection strength is taken into account. And being already there, how to fake the light attenuation/scattering in water so it is not crystal-clear but has more realistic color.

1. The relation of reflectivity and viewing angle

If you imagine looking at water body from different angles it should be obvious, that the lower is viewing angle the more light it reflects. Sea may look almost like perfect mirror during tranquil sunset - but if you are looking daytime from the top of a cliff, you can see the blueish-greenish color of water and only a little reflection.

The reflectivity of water comes from the difference in refractive indexes of air and water. As the speed of light is different in these mediums, some light is reflected and the light entering water changes slightly its direction - the latter is called refraction. Refraction is another phenomenon that can add realism, but we will not try to simulate it here.

A schematic diagram of reflection and refraction

Mathematically the amount of light reflected from the surface of water is described by Fresnel equations:

Fresnel reflection equations (source Wikipedia)

Rs and Rt are the reflectance values of vertically and horizontally polarized light.
θi and θt are the angles between the surface normal and incident and refracted rays.

n1 and n2 are the refractive indices of two media - in our case air and water. The relevant values are:

n1 = 1.000277 ≈ 1

n2 = 1.3330

We do not need θt because it can be derived from θi and refractive indices using Snell's law - look at the rightmost part of equations.

The reflectance values are different for differently polarized light. This explains the magic behind anti-glare sunglasses and optical filters - they cut off vertically polarized light, that is much more strongly reflected.

It is also interesting to know that skylight is in fact somewhat polarized. But for our simulation we ignore this and treat all light as the uniform mix of both polarizations. In that case, the total reflectance can be simply calculated as:

R = (Rs + Rt) / 2

The full Fresnel equation above is a bit too complex for our shaders. It is physically correct - but our goal is natural or good-looking scene and we are ready to sacrify a little here ad there to save shader instructions for other things.

There is quite simple approximation available. Take a look at the following graph:

Fresnel reflectance values Rs, Rp and R (blue, red, yellow) and our approximation (green)

The green line represents function:

R = Rmin + (1 - Rmin) * (1- cos θi)⁵

That can be used as good approximation.
Rmin is 0.02 for real water, but you may want to increase it to something like 0.1 or even more, unless you have very good HDR implementation. The problem is that real sky is really bright - if you are using dimmed down version of sky, its reflection is not visible at all from high angles.

That's it. Now we have reflectance value calculated - but we cannot yet update our shaders. Unlike in our previous lesson, where the reflection was all that had to be rendered, we now have to render the water itself too - unless the reflectance is exactly 1.

2. Rendering water

Water is normally dense medium and strongly scatters light. The actual formula is quite complex and depends on the amount of different chemical compounds (such as oxygen, humic acids) and various inorganic (such as clay) and organic (like plankton) particles in water. But our goal is not to simulate procedurally the color and turbidity of water, but instead find a meaningful set of descriptive parameters, that will give us good enough approximation.

Scattering changes the intensity of light (ray) in two ways:

Out-scattering - if ray of light goes through medium, some fraction of light is scattered away from direct path and thus the final amount of light is lower.
In-scattering - as light is scattered to all directions, some light from rays originally going other directions is scattered to the direction of the ray of interest.

Because of out-scattering the bottom of deep water body is dark. Because of in-scattering objects inside water seem "tinted" with water color.

Scattering in water. A - in-scattering. B - out-scattering.

In addition to scattering there is one more phenomenon causing less light to come from water - it is internal reflection. As light hits the bottom of water body or objects inside it and goes upwards from there, some of it is mirrored back into water from the air-water phase surface.
We ignore this at moment and will use shortcut - instead of adding together the light coming from inside water and light from reflection, we draw the latter as semitransparent surface using reflectance as alpha value. Thus the higher is reflectance, the lower is the effect of light from inside water - which is generally correct, because the internal and external reflectance values are correlated.

How good our water formula can be depends on whether we can read the color and depth values of the bottom of water body or underwater objects in shader or not. Here I present a simple approach, that does not use them, but instead adds the color of water to the reflection image.

We ignore the exact scattering equations, that involve multiple integrals and instead combine the "tint" of water with the color of reflection (that is semitransparent now) and then render them as semitransparent surface over the already rendered bottom of water. For this I use a very simple formula:

Ctint = Cwater * (Omin + (1 - Omin) * sqrt (min (thickness / Dopaque, 1)))

Ctint is the color that water adds to objects (premultiplied)
Cwater is the color of opaque water column
Omin is the minimal opacity of water. It should be 0 for realistic simulation, but in reality values 0.1-0.2 give overall better effect.
Dopaque is the depth of water column, that becomes fully opaque. The reasonable value is 2 m for freshwater bodies - the smaller the better, as it helps to hide the lack of refraction.
thickness is the thickness of water in given direction until bottom or some underwater object is hit.

Calculating thickness is tricky. The technically correct way would be to trace ray in refracted direction until bottom (line AC in following figure) - but we cannot afford to do that.
If you can use depth buffer, you can ignore refraction and calculate the distance the original ray would cover underwater (line AD). This overestimates the thickness, but as the effect only becomes noticeable at low viewing angle, where reflection dominates, it should look quite good.
Here I will use even simpler approximation. Just find the depth of water under given point of surface (point B on following figure), and pretend that water has uniform depth (line AB₁). It underestimates depth at the slopes directed away from viewer and overestimates at slopes directed to viewer, but if the bottom of water is reasonably smooth it is not too bad.

A diagram of different possible methods for water thickness calculation

How to get the actual water depth under given point?
Recall the previous tutorial. We set the Z coordinate of vertex to 0 (i.e. flatten our object), but kept the full original vertex coordinate in interpolatedVertexDepth.
Thus if the object being rendered as water is actually the bottom of water body, it will render as flat surface, but we have access to the original Z coordinate of it. In other words - the water depth.
Another approach would be to encode water depth into another vertex attribute. It has some good points - like no need to separate the bottom of water body from other terrain and the possibility to hand-code depth.

Once we have calculated water thickness with whatever method applicable, we treat the tint color as another semitransparent layer, lying directly beneath the reflection layer. The final color and alpha values can be calculated by standard alpha blending formula:

C = A_reflection * C_reflection + (1 - A_reflection) * C_water
A = A_reflection + (1 - A_reflection) * A_water

Where C and A are color and alpha values.
If the resulting alpha is below 1, bottom or underwater objects are partially visible.

3. Shaders

There is no need to change vertex shader.

Fragment shader:

uniform mat4 o2v_projection_reflection;
uniform sampler2D reflection_sampler;
uniform vec3 eye_object;
uniform float min_opacity, opaque_depth, opaque_color;

varying vec3 interpolatedVertexObject;

void main()
{
    // Vertex on water surface
    vec3 surfaceVertex = vec3(interpolatedVertexObject.xy, 0.0);
    // Reflection angle
    vec3 vertex2Eye = normalize (eye_object - surfaceVertex );
    float cosT1 = vertex2Eye.z;
    // Reflectance
    float c = 1.0 - cosT1;
    float R = min_reflectivity + (1.0 - min_reflectivity) * c * c * c * c * c;

    // Water density
    float depth = -interpolatedVertexObject.z;
    float thickness = depth / max (cosT1, 0.01);
    float dWater = min_opacity + (1.0 - min_opacity) * sqrt (min (thickness / opaque_depth, 1.0));
    // Premultiply
    vec3 waterColor = opaque_color * dWater;

    vec4 vClipReflection = o2v_projection_reflection * vec4(interpolatedVertexObject , 1.0);
    vec2 vDeviceReflection = vClipReflection.st / vClipReflection.q;
    vec2 vTextureReflection = vec2(0.5, 0.5) + 0.5 * vDeviceReflection;

    vec4 reflectionTextureColor = texture2D (reflection_sampler, vTextureReflection);
    // Framebuffer reflection can have alpha > 1
    reflectionTextureColor.a = 1.0;

    // Combine colors
    vec3 color = (1.0 - R) * waterColor + R * reflectionTextureColor.rgb;
    float alpha = R + (1.0 - R) * dWater;

    gl_FragColor = vec4(color, alpha);}

We have added another uniform (in addition to water color and opacity ones) - eye_object, that is simply camera position relative to water object local coordinate system.

And real-time image from Shinya:

Simple scene from Shinya with partial reflection and water opacity

Now it is a bit better than last time - but still artificial and lifeless. Next time I show, how to make it live - i.e. add waves or ripples.

Part 1 - reflective surface

Have fun!

Reflective water with GLSL, Part I

2011-09-16T22:43:00.000+03:00

Being it for physical accuracy or setting mood in game, water and reflections are something that can add lot to your rendering engine. While true reflections can only be done with ray-tracing, one can achieve surprisingly nice approximations by using quite simple scene setup and some GPU programming.

Good water simulation should have at least the following features:

True reflection (with correct parallax)
Clipping of underwater objects on reflection image
View angle dependent transparency/reflectivity of water
Ripples and/or waves
Water scattering (i.e. water becoming gradually opaque as depth increases)

Some more things, that can make things nicer but are not as visible, are:

Refraction
Caustics - i.e. light spots at the bottom of shallow water
Reflected light - i.e. light spots reflected to objects near water

At moment I have only implemented features from the first list into Khayyam/Sehle/Shinya code. You can look at my previous post for some in-engine images.
Here I will describe the mathematics behind the scenes and give step-by-step guide to writing your own water system/object/rendering pass.

1.Rendering reflection texture

Water without reflection looks totally uninteresting - just like any other semitransparent surface. Thus we start from implementing reflection and later go on to other effects.

1.1. Parallax
Even if you have until now managed to render you scene in single pass, from this point on you need at least two passes (actually at least N+1, where N is the number of visible reflective surfaces).

The reason is, that unfortunately we cannot recycle our main scene image for reflections. First because it could make view frustum insanely large (for example - if viewing the water surface from high angle we see only ground and water in our main view, but mostly sky in reflection). And second because of parallax. The reflection is unfortunately not the perfect copy of reflected scene, but copy of the view of the same scene from different viewpoint. The following image illustrates this.

A diagram explaining the parallax effect on reflected image

It means that you need to have rendering to texture set up and working. We will render reflection to texture and later use this texture while rendering the water surface in main scene.

Thus, to get reflection texture we first have to render our scene from the reflected camera viewpoint P' to texture. First we have to find the reflected camera position - or more precisely the reflected view matrix (because we need camera orientation too in addition to the position).
This can be done with the following formula:

M'camera = Mreflection * Mcamera

Where Mreflection is the reflection matrix of mirror surface. It can trivially be calculated from the position of reflection plane:

              | 1-2Nx2   -2NxNy  -2NxNz  -2NxD |
Mreflection = |  -2NxNy 1-2Ny2   -2NyNz  -2NyD |
              |  -2NxNz  -2NyNz 1-2Nz2   -2NzD |
              |    0       0       0       1   |

Where (Nx,Ny,Nz,D) are the coefficients of plane equation (xNx + yNy + zNz + D = 0). Notice, that (Nx,Ny,Nz) is also the normal vector of given plane.

Mcamera is the transformation of camera as if it would be "normal" object in scene. To get ModelView matrix you will need the inverse of it.

1.2. Mirrored geometry

Actually we cheated a little in the previous image. We rotated the mirrored image 180º to make it more similar to the original image, so the effect of parallax can be seen. The actual mirrored image looks like this:

Different winding order on mirrored image

Notice, that the winding order of polygons in image is flipped on mirrored image - i.e. the triangle is oriented CCW on original but CW on reflection.

This may or may not be problem for you. If all your materials are double sided (i.e. you do not do back face culling) or if you can set up rendering pipeline in such a way, that you can change culling direction it is OK. In my case though, I prefer to keep culling always on and have forward-facing always defined as CCW. So something has to be done with the reflected image - or otherwise geometry will not render properly.

We will exploit the feature that camera is always (at least in most applications) rectangular and centered around view direction. Thus we can just flip camera in Y direction and the winding order will be correct again (it flips reflected image so it looks like (3) on the first picture).
This can be done with one more reflection matrix:

M''camera = Mreflection * Mcamera * Mflip

Where Mflip is simply another reflection matrix that does reflection over XZ plane.
Now if we render mirrored image using M''camera as camera matrix, pipeline can be left intact. We, of course, have to save this matrix for later reference, because it is needed to properly map our texture to water object in main render stage.

1.3. Underwater clipping
Take a look at the following picture:

A reflection with underwater object

We have added an underwater object Q to our scene. Now it should not appear on reflection, because it does not block the actual reflection rays PB'B and PA'A. But we are not doing ray-tracing. We are instead moving camera to mirrored viewpoint P' and rendering reflection like normal image. But as you can see, the object Q blocks ray P'A'A and thus would show up in our reflection.

Thus we have to make sure, that nothing that is under the reflection plane (water surface) will show up in mirror rendering. This can be achieved in three different ways:

Use additional clipping plane on GPU. It can be very fast or very slow - depending on card and driver used.
Use oblique projection matrix during reflection rendering. You can read more about it here. This is cool technique, but personally I have never got it to work well enough because it messes up camera far plane.
Clip manually in pixel shaders. It wastes some GPU cycles, but is otherwise easy and foolproof.

I went with option (3) because oblique projection matrix did not seem to play well with wide camera angles (far plane moved through infinity creating all kinds of weird effects). The clipping itself is as easy as adding the following code at the beginning of all pixel shaders (or more precisely the ones that are used for reflectable objects):

uniform vec4 clip_plane;
varying vec3 interpolatedVertexEye;

void main()
{ 
    float clipPos = dot (interpolatedVertexEye, clip_plane.xyz) + clip_plane.w;
    if (clipPos < 0.0) {
        discard;
    }
...
}

Of course you have to supply your shader with clip_plane and calculate interpolatedVertexEye in vertex shader (it is simply vertex coordinate in view/eye space: VertexEye = Mmodelview * Vertex). If you do not need clipping, simply set clip_plane normal (xyz) to zero and all pixels will be rendered.

1.4. Putting it all together
Before starting the main render pass (being it forward or deferred) do the following:

Create list of all objects that need reflections (and the parameters of all reflection planes). Then for each reflection plane:
Calculate the reflected camera matrix
M''camera = Mreflection * Mcamera * Mflip
Set up camera matrices (you can optimize rendering by using clipped projection matrix, but this will not be discussed here).
Set clipping plane to reflection plane
Render full scene
Save the rendered image as texture to be used with reflective object

If you are using HDR you should not tone-map reflection texture - unless you want to achieve some very specific effect.

2. Rendering reflective object

This is actually quite easy - provided that you have at hand all necessary parameters. You have still to decide at which render stage to do this. I use transparent stage, as water is basically just one semi-transparent surface in scene, but you can add another pass before or after transparency as well.

You will need at hand:

Reflected camera matrix M''camera
Projection matrix you used to render reflection Mprojectionreflection (normally this is the same projection that you use for main camera)
Reflection texture

2.1. Vertex shader

attribute vec3 vertex;

uniform mat4 o2v_projection;

varying vec3 interpolatedVertexObject;

void main()
{
	gl_Position = o2v_projection * vec4(vertex.xy, 0.0, 1.0);
	interpolatedVertexObject = vertex;
}

We add another constraint here - water surface will be at XY plane of the object local coordinate system. It is strictly not necessary if you have the proper reflection plane, but I found it easier that way. Just use XY plane as reflection plane and place your object (water body) appropriately.

Actually this allows us to do another cool trick. We can use the bottom of water body (i.e. river, lake..) as our water object. It will be flattened in shader, but we can use the Z data to determine the depth of water at given point. But more about this in next part.

o2v_projection is simply my name for composite matrix Projection * ModelView. I prefer to name matrices with mnemonic names, describing the coordinate system transformations they do - in given case it is Object To View, multiplied with Projection.

interpolatedVertexObject is simply vertex coordinate in object local coordinate system - we will need it to do lookup onto reflection texture.

2.2. Fragment shader

uniform mat4 o2v_projection_reflection;
uniform sampler2D reflection_sampler;

varying vec3 interpolatedVertexObject;

void main()
{
	vec4 vClipReflection = o2v_projection_reflection * vec4(interpolatedVertexObject.xy, 0.0 , 1.0);
	vec2 vDeviceReflection = vClipReflection.st / vClipReflection.q;
	vec2 vTextureReflection = vec2(0.5, 0.5) + 0.5 * vDeviceReflection;

	vec4 reflectionTextureColor = texture2D (reflection_sampler, vTextureReflection);

	// Framebuffer reflection can have alpha > 1
	reflectionTextureColor.a = 1.0;

	gl_FragColor = reflectionTextureColor;
}

o2v_projection_reflection is the composite matrix Projection * ModelView as it was used during reflection rendering. I.e:

Mprojectionreflection * (M''camera)-1 * Mobject

Like the name implies, it transforms from the object coordinate system to the clip coordinate system of reflection camera.

In fragment shader we simply repeat the full transform pipeline during reflection rendering and use final 2D coordinates for texture lookup. For this we need initial, untransformed object vertices - thus they are interpolated from vertex shader (interpolatedVertexObject).

I'll set reflection alpha to 1.0 because I use HDR buffers and due to additive blending the final alpha can have some very weird values there.

And the rendered image:

Simple scene from Shinya showing water as perfect mirror

Not very realistic?
Up to now we have implemented water as perfect mirror. This is very far from reality (look at the feature list in the first section).

In the next parts I will show how to add viewing angle based transparency, water color and depth-dependent ripples to your water.

Have fun!

GLSL water reflections

2011-08-29T01:40:00.000+03:00

I have been mostly working on sehle (Khayyam rendering engine) based game framework lately. There have been some new things in Khayyam - that will be the scene/level builder for it - as well. The latest addition is reflective water material.

Esk standing on near water - with ripples and reflection

You can convert all static objects (OBJ, 3DS and Collada) to water bodies - although to get realistic results, they should be bowl- or plane shaped with surface at Z zero (in object coordinates). Everything is fake, of course - there are no real waves or refraction, but only distorted reflections and transparency. But it still looks reasonably good in my opinion.

At moment there are following water properties implemented:

Full reflection (everything that can be rendered can be reflected, except other reflective surfaces)
Viewing angle based reflectivity - i.e. if looking directly down, water is mostly transparent, looking along water surface it becomes almost perfect mirror
Depth-based transparency - shallow water is almost transparent, deeper water becomes opaque
Up to 8 simultaneous ripple generators, that can be assigned to "shore" vertices of water body

At the image below you can see how the water color changes from almost fully transparent near bank to completely opaque brown at the middle of river. As the viewing angle is high, overall reflectivity is low and the colors of river bottom and water can be seen. Ripples change the apparent angle between viewer and water surface, so although sky is uniform color, ripples still show as they change the reflectivity of surface.

A river from above showing water and bottom colors

At the next image the viewing angle is low and thus the surface of water is almost completely reflective.

A river from low angle, showing almost perfect mirror

Ripples are circular and their wavelengths, amplitudes and generation points are updated randomly over time. Thus the actual pattern almost never repeats - although sometimes it is not as nice as on the image above.

When I find some free time, I'll write the technical details about the actual mathematics in shaders. And hopefully there will be new Khayyam release too.

Have fun!

Encoding normals for Gbuffer

2011-07-18T03:54:00.000+03:00

Deferred shading has nowadays become nearly ubiquitous in real-time rendering due to the separation of geometry and lighting passes. The general idea of this technique is to render all important properties (color, normal, reflectivity and so on) of all visible surfaces to a set of screen-sized textures. Later rendering passes (lighting) get surface parameters from those textures and thus complex geometries do not have to be rendered multiple times.

One design problem of Gbuffer implementation is the efficient encoding of surface normals. Normals in three-dimensional space have three components:

N = Nx,Ny,Nz

The most intuitive way would be to store those in three texture channels. But this would be wasteful, because we know, that:

Nx2 + Ny2 + Nz2 = 1

Gbuffer requires many texture channels for other data, thus we want to cut off as many unnecessary channels as possible to conserve memory and fillrate.

Another simple alternative would be to store only two components (Nx and Ny) and reconstruct third (Nz) in pixel shader. Unfortunately we will lose the sign of Nz in that process. While in ideal scene there should be no normals with negative Z (facing away from camera), they happen in real scenes because of realistic polygon counts.

There exist several techniques for encoding normals while (at least partially) preserving Z component. Unfortunately no one of those is ideal. Either they are not able to encode full range of Z (various projections) or waste precision and calculation (polar coordinates).

While implementing foliage shader for Khayyam I needed a way to encode full range of possible normals into two-component vector (that will later be stored in 4-component 8-bit RGBA texture of Gbuffer). The following is the brief introduction of the technique used. It solves all the problems I am aware of - with the price of slightly more shader instructions than simple projection encoders.

Efficient projection of normal space

We forget for awhile the need of storing the sign of Z component and look, how we can store X and Y components most efficently.
The trivial way is to simply forget Z and store X and Y. In geometric terms it means projecting the hemisphere of normal space to an unit circle on XY plane along Z vector as in following figure:

The trivial projection of normal space to XY plane

The problem with this projection is, that the uniform angular difference between normals near equator gives much smaller difference in X and Y coordinates than near poles. If the precision of normal texture is limited to 16 bits (4x8 bit or 2x16 bit integer buffers) or even less (FP16 buffers) , the loss of precision may become visible. For example, for 16 bit buffers, the minimum representable angle near equator is:

acos (1 - 2e-15) = 1.44°

Near poles it is much better:

asin (2e-15) = 0.002°

Clearly we are wasting precision near poles and introduce errors near equator.

To get better distribution of precision, we can switch projection from parallel to radial, with the projection center at the point (0,0,-1) as on the following figure:

The radial projection of normal space

The distribution of angles is still not uniform but is clearly much better (it differs only by the factor of 2 at poles and equator).
Actually, having the center of projection at (0,0,-sqrt(2)) would result in even better distribution, but I wanted to keep it at (0,0,-1) to simplify calculations a bit.

The hemisphere is still projected at unit circle at XY plane, although now we cannot project the normals on negative hemisphere directly but have to take the absolute value of Z coordinate before projecting.

This solves the problem of effecient use of normal texture precision. Now we can go on to encoding the sign of Z into the same buffer.

Encoding the sign of normal Z coordinate

Our positive hemisphere of normal space got projected to unit circle on XY plane as in following figure:

The normal space projection to XY plane and compaction schema

As we can see, we are actually wasting the numerical space of normal texture. The texture is able to encode values in unit square, but only unit circle is used - the possible values on dashed areas can never happen in our projected normals. We could store normals with negative Z in those areas, but unfortunately there is no easy algorithm to do that.

Now we do another conversion and pack all the values from unit circle into diamond-shaped area, given by the following formula:

|X| + |Y| <= 1

This can be done with the following algorithm (let the normal be Nx', Ny' and the projection be Nx'', Ny''):

r = sqrt (Nx' * Nx' + Ny' * Ny')

D = |Nx'| + |Ny'|

Nx" = Nx' * r / D

Ny" = Ny' * r / D

We lose some precision at the normals close to 45° angles, but the maximum loss is by the factor of sqrt(2).

The resulting projection of normal space is shown in following figure:

Compacted normal space and Z flipping directions

Now the whole projection of the positive hemisphere of normal space takes exactly the half of the size of unit square. The extra space can be used to encode normals with negative Z.

We do this by mirroring the final normal projections by the closest one of diagonal lines (|x| + |y| = 1).

Thus we have encoded the full normal space to unit square with minimal loss of precision.

Decoding normals

To decode normals we have first to find the sign of Z coordinate. This is done with the following formula:

Zsign =  1 if (|x| + |y|) <= 1

Zsign = -1 if (|x| + |y|) >  1

Now, if Z is negative, we have to mirror our encoded normal by the closest diagonal line (|x| + |y| = 1) so the resulting normal is inside the diamond shaped area.

We unpack normals to unit circle with reverse packing algorithm:

d = sqrt (Nx" * Nx" + Ny" * Ny")

r = |Nx"| + |Ny"|

Nx' = Nx" * d / r

Ny' = Ny" * d / r

From normal projection on unit sphere (N') unit sphere we unproject to normal on positive hemisphere (N).

Finally we set the sign of the Z component of N from previously found Zsign.

And that is it.

Encoding quality

I ran simulated tests of this algorithm on CPU with 100 000 000 randomly generated normals, including normals with any 1 or 2 components zero. Encoded vector was written and then read back from 4-component unsigned char buffer to simulate storing of 2-component normal in RGBA8 texture.

The maximum angular error between original and retrieved normal was 0.028°.

GLSL shader code

For those interested, here is current GLSL shader code of libsehle implementation. It is a bit heavy, but if your lighting is fill-rate bound, as is mine, you can spare some GPU cycles.

Encoding.

vec2 encodeNormal (vec3 normal)
{
    // Project normal positive hemisphere to unit circle
    // We project from point (0,0,-1) to the plane [0,(0,0,-1)]
    // den = dot (l.d, p.n)
    // t = -(dot (p.n, l.p) + p.d) / den
    vec2 p = normal.xy / (abs (normal.z) + 1.0);

    // Convert unit circle to square
    // We add epsilon to avoid division by zero
    float d = abs (p.x) + abs (p.y) + EPSILON;
    float r = length (p);
    vec2 q = p * r / d;

    // Mirror triangles to outer edge if z is negative
    float z_is_negative = max (-sign (normal.z), 0.0);
    vec2 q_sign = sign (q);
    q_sign = sign (q_sign + vec2 (0.5, 0.5));
    // Reflection
    // qr = q - 2 * n * (dot (q, n) - d) / dot (n, n)
    q -= z_is_negative * (dot (q, q_sign) - 1.0) * q_sign;

    return q;
}

Decoding.

vec3 decodeNormal (vec2 encodedNormal)
{
    vec2 p = encodedNormal;

    // Find z sign
    float zsign = sign (1.0 - abs (p.x) - abs (p.y));
    // Map outer triangles to center if encoded z is negative
    float z_is_negative = max (-zsign, 0.0);
    vec2 p_sign = sign (p);
    p_sign = sign (p_sign + vec2 (0.5, 0.5));
    // Reflection
    // qr = q - 2 * n * (dot (q, n) - d) / dot (n, n)
    p -= z_is_negative * (dot (p, p_sign) - 1.0) * p_sign;

    // Convert square to unit circle
    // We add epsilon to avoid division by zero
    float r = abs (p.x) + abs (p.y);
    float d = length (p) + EPSILON;
    vec2 q = p * r / d;

    // Deproject unit circle to sphere
    float den = 2.0 / (dot (q, q) + 1.0);
    vec3 v = vec3(den * q, zsign * (den - 1.0));

    return v;
}

More about Matrix to Euler angles conversion

2011-06-13T02:47:00.001+03:00

I previously posted the algorithm to convert rotation matrix to arbitrarily ordered Euler angles.
It solved two problems of the trivial conversion method in Matrix and Quaternion FAQ:

Use arbitrarily ordered axes (like ZXY) in addition to XYZ
Remove the discontinuity happening at Ax = +/- 90 degrees

Meanwhile I discovered two remaining problems with my implementation:

The algorithm always return the minimum set of absolute Euler angles (closest to {0;0;0}, as defined by the sum of squares of the angles) from the two alternatives. Often it is desirable to get the set of angles that are closest not to identity {0;0;0} but to some predefined rotation {Rx;Ry;Rz}.
When gimbal lock occured, the X rotation (or corresponding rotation if axes were reordered) was set to zero. This may not be the best solution, if we need the Euler angles to be as close to some specific set of values as possible.

The problem surfaces if we want to describe animations by Euler angles to allow easy adjustments by IK solvers (and have joint constraints defined) and interpolate between keyframes. In that case we absolutely have to keep the angles of adjacent keyframes as similar as possible - because although the alternate sets of angles make identical matrices, interpolations between them generally do not.

Stable conversio of matrix to Euler angles closest to given set

The matrices have row-major order, so they have to be transposed for OpenGL.

Base is a set of three angles {Bx;By;Bz} that will be used as reference while determining the best set of resulting angles.

void
Matrix3x4f::getEulerAngles (f32 angles[], const f32 base[]) const
{
 float aX, aY, aZ;
 float aX2, aY2, aZ2;

 aY = asin (c[2]);
 aY2 = (aY >= 0) ? M_PI_F - aY : -M_PI_F - aY;
 if (fabs (c[2]) < 0.99999f) {
  // Over 0.25 degrees from right angle
  float C = cos (aY);
  float C2 = cos (aY2);
  float trX = c[10] / C;
  float trY = -c[6] / C;
  aX = atan2 (trY, trX);
  aX2 = atan2 (-c[6] / C2, c[10] / C2);
  trX = c[0] / C;
  trY = -c[1] / C;
  aZ = atan2 (trY, trX);
  aZ2 = atan2 (-c[1] / C2, c[0] / C2);
 } else {
  // Less than 0.25 degrees from right angle
  // Gimbal lock occured
  aX = aX2 = base[0];
  // Keep X rotation the same as base
  float Sx = sin (aX);
  float Cx = cos (aX);
  if (fabs (Cx) > fabs (Sx)) {
   float Sz = (c[4] + (Sx/Cx) * c[6]) / (Sx*Sx/Cx + Cx);
   aZ = aZ2 = asin (Sz);
  } else {
   float Sz = (c[6] + (Cx/Sx) * c[4]) / (Cx*Cx/Sx + Sx);
   aZ = aZ2 = asin (Sz);
  }
 }

 float d1X = clamp_pi (aX - base[0]);
 float d1Y = clamp_pi (aY - base[1]);
 float d1Z = clamp_pi (aZ - base[2]);
 float d2X = clamp_pi (aX2 - base[0]);
 float d2Y = clamp_pi (aY2 - base[1]);
 float d2Z = clamp_pi (aZ2 - base[2]);

 if ((d1X * d1X + d1Y * d1Y + d1Z * d1Z) < (d2X * d2X + d2Y * d2Y + d2Z * d2Z)) {
  angles[X] = aX;
  angles[Y] = aY;
  angles[Z] = aZ;
 } else {
  angles[X] = aX2;
  angles[Y] = aY2;
  angles[Z] = aZ2;
 }
}

If aY is close to +/- 90 degrees (gimbal lock occured) we want to set aX to the base value instead of setting it to zero.
Also we calculate the differences of both alternate sets of angles from base and choose the final set based on the squared sum of those differences.
Clamp_pi simply converts angle to -PI...PI range.

Conversion of matrix to arbitrarily ordered Eular angles

The matrices have row-major order, so they have to be transposed for OpenGL.

Order is array of three integers, determining the order of rotations ({0;1;2} is XYZ, {2;0;1} is ZXY).
Base values should be ordered according to order.

void
Matrix3x4f::getEulerAngles (f32 angles[], const int order[], const f32 base[]) const
{
 float sign = ((order[1] == (order[0] + 1)) || (order[2] == (order[1] + 1))) ? 1.0f : -1.0f;
 // Permute matrix to switched axes space
 Elea::Matrix3x4f rs;
 for (int row = 0; row < 3; row++) {
  for (int col = 0; col < 3; col++) {
   rs[4 * row + col] = c[4 * order[row] + order[col]];
  }
 }
 rs[2] *= sign;
 rs[6] *= sign;
 rs[8] *= sign;
 rs[9] *= sign;
 // New base
 float nbase[3];
 for (int i = 0; i < 3; i++) nbase[i] = base[i];
 nbase[2] *= sign;
 // Decompose to Euler angles
 rs.getEulerAngles (angles, nbase);
 angles[2] *= sign;
}

The trick is to permute the rotation matrix in such way, that the XYZ angles of new matrix are properly ordered decomposition angles of the original matrix and then do the trivial decomposition.
Hopefully this time the algorithm is final ;-)

Have fun!

The future of Khayyam

2011-04-05T01:04:00.001+03:00

Khayyam 3D did not have very clear beginning. Few years ago I was experimenting with 3D rendering and animation under projects codenamed Floyd and SDLMu. The initial impulse was to write an engine and scene editor for my Ant-Attack inspred game.
The unorganized codebase soon grew out of control, so I started from scratch. Or more precisely ported the program structure from my former project Sodipodi. When choosing name for the new project, I discovered Omar Khayyám - a Persian mathematician, who sort of discovered the inherent link between geometry and algebra. And thus the program was born.

As of now, Khayyam is evolving in several directions based on what I am interested in any given moment.

Scene builder. My game is still in design stage, but at least I have the main character - Sara.
Virtual photography tool. It was partially inspired by HongFire hentai game modding community and partially by Poser and DAZ applications.
Animation editor. This came from the need for some decent animations for Sara.
Model importer and converter. Implemented step-by step as needed.
3D engine. Mostly for learning, but also because I think I have some ideas, how it can be done right.

As of now (April 2011) the program has at last become sort of usable for some simple tasks, like converting model formats, building POV-Ray scenes and so on. To go further, there should be a somewhat clearer working plan - which I have tried to lay out for myself.

1. Scene builder

Khayyam itself is not game engine and never will - the two-level DOM structure is too heavy for gameplay. Instead there will eventually be an engine based on libsehle.
There will be custom object formats. At least an octree-based map node, skeletal figures and static objects. Those can be imported from Blender Collada files, optimized and written to custom format.
Objects need JavaScript bindings. I plan to make JavaScript the scripting language for game engine, so the actions should be programmable and testable in Khayyam.

2. Posing application

The Poser figure loading and manipulating is still very flaky. This will get better eventually, so expect that in some future date Khayyam will be able to render (with the help of POV-Ray) everything Poser and DAZ studio can. Virtual photography is becoming more and more used, and Linux definitely needs a free application for that. The fist milestones are unlit objects (like backgrounds) and smoothscale channel implementation for full body morphs.

3. Animation editor

Animations will be integrated globally into Khayyam document structure, so you can render not only still pictures, but full animation sequences.
I am halfway implementing animation graph and biped walking controller for figures. Eventually you could import animations from other formats (like Biovision BVH), define sequences, merge, split, edit and join them, and build fully controllable animation graph from these. The controller will have IK solvers for fine limb/finger adjustments and will be controllable via JavaScript.

4. Model converter

While several popular models are supported, the actual features vary a lot. There will be more model and animation formats (like MD5 animations) and more features. I also plan to support more game model formats - definitely all future Illusion games, but probably some others too.

5. 3D engine

The big missing parts are proper shadow map algorithms, particle effects and post processing.

Other than that, Kahhaym will have some UI overhauls in future. Tools will have their own dynamic property pages. Some extra tools, like bone and object pickers are needed. And there have to be UI controls for constraint placement. Also I am particularly not happy with Gtk+ default style - which wastes enormous amount of screen space. At least the animation editor needs more compact style

Sara and african elephant (DAZ 3D model)

Have fun!

How to convert animations in Khayyam

2011-04-04T00:06:00.000+03:00

Starting from the 20110402 release Khayyam can import, convert and export Biovision BVH animations from one figure/skeleton to another. Following is a mini-tutorial guiding you through the process.
You may take a look to the overview of pose fitting algorithm to better understand which joints will be moved and how.

0. The example problem

Say, you have some good animations in BVH format and want to apply these to Poser characters. Unfortunately, skeleton topologies and/or bone orientations do not match, so they are not usable as-is.
Khayyam can actually export BVH files from supported animation types (currently only Illusion game formats). How to do this is outside of this tutorial - but as a hint look at skinAnimation and sequence objects in document tree editor.

1. Setting up target

Before we can convert animation to target figure, we need it's skeleton imported into Khayyam. Skeleton comes together with model, so at first we have to import Poser cr2 figure.
It is probably good idea to use reduced resolution figures for this process, because animating the whole iteration 4 (V4, M4) models can be quite slow. I will use Chibibel for current example - she has much lower polycount and can show animations without too much frame-skipping.

Chibibel imported to Khayyam

At moment Khayyam does not set up joint constraints automatically for cr2 objects, so you have to define at least elbow and knee constraints. Otherwise you risk, that legs or arms may suddenly bend sideways during animation.
Select imported figure, switch to pose mode and select left shinbone.

Chibibel skeleton with shinbone selected

The colors of rotation arrows mark the bone-relative axes of rotations (red - X, green - Y, blue Z). Normally knee bends only in one direction - in current case this is green rotation, i.e. Y axis. So you have to disable X and Z rotations.

Open document tree dialog. It will automatically show property page for selected bone - i.e. left shin.

The property page of left shinbone

In constraints frame select first X, then Z channel and uncheck the Enabled box for both. This turns off the rotations around those axes.
On the same page you can set more fine-grained behavior by defining tension parameters for bones. Angles are basically maximal allowed rotations in either direction, rigidity values control, how "difficult" is given rotation. For example, knee joint moves very easily (in allowed range), but twisting shoulder is difficult, so character tries to minimize it. But if the pose is not achievable otherwise, the twisting still can happen - unlike the hard cutoff angles, that cannot be exceeded.
In current example we fortunately do not need to set up tensions.
Repeat the disabling X and Z channel rotations for right shinbone. Then select left forearm and disable X and Y rotations. The same with right forearm.
Now we have completed the minimum setup needed for successful pose merge.

2. Converting animation

In document tree select the main figure node. From the property page click on Merge animations... to open the converter dialog.
The first step is to load source animation or pose. Click Load animation... and select your BVH file.

Running animation applied to Chibibel skeleton

Once the animation is loaded, Khayyam tries to adjust the destination figure to starting pose. This is iterative process and may take more than one try. So if the pose is not close to the original, you may try to click Adjust pose few times.
The red armature is the original animation skeleton. The blue one is the skeleton of target figure. These can be toggled on and off to see clearer picture.
The other controls you may tweak are:

Scale - changes the size of source skeleton. This should be used (together with ZScale) to make the skeletons approximately the same height - otherwise shoulders and hips can not be posed correctly.
ZScale - changes the height of source skeleton. Thus Scale can be used to make the widths of hips and shoulders approximately right, and ZScale then to make the height of character right.
Guess scale - Khayyam tries to determine scale from the distances between hips and shoulders. This may or may not work correctly.
EMax - tha maximum error tolerance - if the combined distance between poseable chains (body, limbs...) is less than EMax, iterative pose refinement will stop. Smaller value may give better adjusting but makes the process slower.
TScale - the scaling factor of bone tensions. Usually this can be 1 for default tensions or some smaller value (0.01) if all tensions have been set up in skeleton.
Runs - number of distinct runs of IK solver
Iterations - the maximum number of tries in each run

Playing with these may give better results. If animation is jerky, increasing the number of runs often helps. If limbs do not track the originals well, lowering TScale may help. Experiment!
Also, you should keep in mind, that while hips and shoulders are placed using the absolute positions, other joints are adjusted by directions. Previous blog entry describes the process in more detail.
Khayyam knows the bone names of some common skeletons and can determine the corresponding standard parts automatically. But sometimes it may not know, which standard humanoid bone certain name corresponds to. In that case you have to define bone names manually, using the bone mapper tool. This can be done by clicking Map buttons in source and destination skeleton frames.
Not all skeletal bones are 1:1 mappable and this is not even needed. What is important is, that standard joints of movable body parts are mapped correctly.

Bone mapper dialog for Poser skeleton

In the example above, you can see the bone mapper dialog for standard Poser biped skeleton (V4, M4, Chibibel). In the left-hand tree there are all bone names that appear in skeleton file, at right are the corresponding Khayyam standardized body parts. Once set up the mapping can be saved and loaded (actually the last saved mapping will be loaded automatically).
Once the bone mappings are set up (and saved), click Close and the conversion solver will update itself.
You can play the animation with current conversion parameters using play button.

3. Importing animation to document

Once you are satisfied with the conversion results, click Import. Khayyam will then generate a tree of animation objects as child nodes of parent Figure node.
Hint: You can set NRuns to bigger value and EMax to lower value for import so the actual conversion will be done with maximal accuracy.
The object of interest for us is a sequence node, that will be created as the last child of figure. It defines the imported animation sequence and can be played from play button on its property page.

The imported animation sequence object

If the imported sequence works as intended, you can export it to new BVH file. This new file uses already the proper skeleton of the target figure.

And that's it. I have many ideas how to make this process smoother, so stay tuned!

Snapshot release 20110402

2011-04-03T01:46:00.000+03:00

A new snapshot release 20110310 is available from SourceForge page as source tarball and precompiled Win32 binary.

The most important new feature is refactored biped pose/animation converter:

Both animations (from BVH files) and static poses (from other objects) can be converted
Animations can be saved to sequences (and exported to BVH again)
Almost all body parts of biped are adjusted (body, limbs, head, fingers)
IK solver parameters can be adjusted
Bone definitions can be set by user (and saved for future use)

Some problems remain - collar bones do not move, you cannot set T-pose and so on.
The better the constraint system of the destination figure, the better pose matching will be. At minimum you should set knee and elbow constraints to avoid wrong bendings.

A demonstration video of making Sara-chan to run. Red armature is the original BVH animation file, blue is the Sara skeleton. It is not ideal, because the BVH does not have finger poses.

Have fun!

Converting animations between skeletons

2011-03-26T12:56:00.001+02:00

I have written one more piece about the skeleton merge about half year ago - you can read it here. What follows is the a much better version of the original algoritm.

The problem

Say you have some good animations (there are many free BVH sites in web) and want to use these for your own models. Unfortunately - unless you made your models using exactly the same skeleton layout, the bones do not match and copying animations is not trivial problem.

There are many ways, how skeletons may differ:

Bone names do not match. This is easy to overcome - either build mapping or rename bones.
Rest pose orientations use different systems (like XYZ euler angles vs. ZXY euler angles vs. quaternions). This is also minor problem, as normally you want to convert everything to quaternions or matrices anyways.
Bone lengths do not match. Thus copying animation directly can make movement unnatural.
Rest pose bone positions (directions) do not match. Thus animations can not be immediately copied between skeletons, but have to be transformed to absolute space (object space) before.
Skeleton topologies do not match. This is often a showstopper, because if you do not even have similar bones, there is no way to copy animations.

Example of different common skeleton topologies

The topology mismatch is the hardest problem to overcome. In the example above, if you, say have animation for the right skeleton, the 4 parts of backbone should move the 2 backbone parts and pelvis of the left skeleton. While in theory it should be possible to solve this problem analytically, it is not easy - and has to be done by hand for each combination of skeletons.
Instead of that, using IK solvers gives us easier way to map those skeletons. It is still not universal - the mapping algorithms have to be adjusted to object itself - in current case a humanoid. But normally this is not big problem, because in 99% cases humanoid is precisely what you want to animate.

In any case you need good IK solver, that can do at least 6-7 bones long chains, adjust both positions and rotations and use both absolute positions and bone directions for targets. Also, the solver has to support comparing up to 4 target points or directions simultaneously. I am currently using simplex method in Khayyam (the code is in helpers/ik.cpp), but there are other options as well.
Also the skeleton should have bone constraints defined - otherwise you may discover that elbows or knees will be bent to completely wrong direction.

We start implementing the algorithm by a small observation. Namely - while there are different ways to construct skeletons, the joints have to be still placed to precise spots - otherwise the movement of joints will not be natural. Thus we can use the joints as anchor spots for the algorithm.

The body

The first and hardest part is moving the main bodies of skeletons to the same position. First - the root bones may be arranged differently. Second - root bones may be joined with body either below or above pelvis. Third - there may be different number of backbone elements. Fourth - there may or may not be extra bones, like hips or collar bones.
To solve this problem, we can do the following:

Set 4 IK target points to the corner joints of body - both hips and both shoulders.
Scale the source skeleton so, that the distances between hips and shoulders are approximately the same, as in target skeleton.
Find the topmost common parents of both hips and shoulders Ah and As.
Find the topmost common parent of Ah and As B.
Build rotating IK chain of bones from B to Ah and from B to As, not including B.
Add both the rotations and translations of the rootmost bone R to chain.

The schematics of body IK solver (green: translate + rotate, red: rotate, blue: not moving)

After solving this IK chain, the corner joins of body will be approximately aligned to the original. Normally you do not achieve perfect alignment, because the width of shoulders and hips is different in skeletons - but this is not big problem, because the direction of hip-hip and shoulder-shoulder lines should be aligned.
It is important to do this alignment in one step - otherwise the alignment of hips may involve extensive rotations and translations of root bone R - and you cannot later align shoulders at all.

Limbs

To align limbs, there are two strategies - depending on what we want to achieve.

We can align the endpoints - if we want to model some specific action - like taking some item from table. In thus case the hand will be in correct place - but because the lengths of arms and forearm probably differ, elbow will be off.
Or we can align the directions of bones - for example if modeling hand movement during walking - in that case both elbow and wrist will be off, but the overall look of hand will be more similar.

At the first case it is just ordinary single-target IK solver. Or if you want to keep the elbow/knee direction more similar to original, there should be additional directional target at midpoint.
At the second case, the IK chain has to be solved with two directional targets (shoulder-elbow + elbow-wrist or hip-knee + knee-ankle) simultaneously. Otherwise the topmost bone may turn it to such direction, that 1 DOF joint at midpoint (elbow or knee) cannot move other bone to the right direction.

Palm

There are probably different strategies for adjusting palms. In khayyam I did the following:

Set 4 directional targets from wrist to the topmost joints of fingers
Add the 3 DOF rotations of palm to IK chain
If forearm includes extra rotational bone (like at the skeleton at left), include the axial rotation of it to chain

By solving this chain, the positions of finger joints will be approximately aligned to the original.

Fingers

Fingers can be aligned in the same way as limbs - but here we need three targets instead of two. Also, as the fingertips are normally the end sites, the last target does not coincide with any joint, but has to be placed about 2-3 cm from the last joint along the bone direction.

Head

Head should be placed by adjusting three positional targets - eyes and skulltop. This can become tricky, because many skeletons may not include eye positions at all.

Sara chan in skeleton merge editor (blue: figure skeleton, red: animation skeleton)

At the above picture you can see the results of adjustment of Sara-chan skeleton to Illusion Characolle animated skeleton. Although the skeleton topologies and bone lengths differ, the pose is pretty close to the original.

At moment the skeleton merge works only in CVS version of Khayyam, but expect it in the next release.

Khayyam architecture: libthera

2011-03-16T10:23:00.000+02:00

For a quick overview of all Khayyam subcomponents, look at the introduction.

Overview

Libthera is the backbone of Khayyam document system. It is very simple DOM-like tree of XML nodes, implementing file IO, transactions (think undo and redo) and property, tree and content mutation events.

The schematic layout of Thera object tree

All properties inside libthera tree are simple text strings. Thera nodes do not know anything about the semantics of attributes, content or child nodes. They only serve as the containers of base state for more semantic-aware objects in libmiletos.

Thera::Node

The basic building block of Thera tree is Thera::Node - an object encapsulating XML node (either element, text or cdata). It has the following properties:

Name (only for element nodes)
Backlink to containing document
One or more attributes (key/value pairs, only for element nodes)
Optional text content
Linked list of children
Linked list of eventlisteners

The tree is modified by atomic methods of nodes - content change, attribute change, child insertion, child removal and child reordering. The API is kept as simple as possible - setting attribute to NULL deletes it, using NULL as ref value during child insertion prepends child and so on. The result is true if the action succeeds, false if not.

bool Node::setAttribute (const char *key, const char *value);
bool Node::setTextContent (const char *newcontent);
bool Node::addChild (Node *child, Node *ref);
bool Node::removeChild (Node *child);
bool Node::relocateChild (Node *child, Node *ref);

By default all methods above are allowed on all proper nodes (no attribute change or child management on text and cdata nodes). Actions can be vetoed by event listeners. The idea here is, that thera tree is not typed - all element nodes are similar and do not know anything about the semantic meaning of themselves or attributes. To implement semantic checks, another structure has to be added to thera tree, that can interpret the property changes and veto/allow these. In case of Khayyam, that additional layer is libmiletos scene graph library.

Event system

For each property change (attribute or content change, child insertion and so on) node first invokes query events from linked EventVector list.
EventVector is list of function pointers, which - if not NULL - will be called during mutation events. I did not implement real signalling system for two reasons. First - to keep things simple. Second - normally single Thera::Node is tracked by single Miletos::Object and thus having all listeners in one structure makes perfect sense.

For example, if one tries to change the attribute of Thera::Node, the following happens:

Old and new attribute are compared. True is returned immediately, if they are identical.
change_attribute listeners are called by function pointers from all linked EventVectors. If any of these returns false, attribute is left intact and false returned.
Actual attribute value of Thera::Node is set to new value
attribute_changed listeners are called by function pointers from all linked EventVectors. This is post-mutation callback and thus cannot veto the change anymore.
If no attribute_changed event was installed, downstream_attribute_changed listeners are called from parent node EventVector list.
Containing Thera::Document is notified about attribute change

Normally the libmiletos scene graph objects (subclasses of Miletos::Object) listen to attribute_changed, content_changed, child_inserted and other post-mutation events and update their internal state whenever something changes. The exceptions are two special attributes id and xmlns. As each object in scene graph has to have unique id for reference system to work, the uniqueness of the value of id attribute is checked in change_attribute handler and mutation blocked if new value is not unique. All xmlns changes are blocked, as those change the semantics of object, and would require replacing one scene graph node with another one.

The reason for downstream listeners is to reduce the number of objects, that libmiletos has to implement. For example <color> nodes in Collada tree do not build their of objects (i.e. there is no Miletos::Collada::Color objects) but instead the containing nodes (ambient, diffuse, light nodes and so on) get signalled of color content changes by downstream propagation.

Transactions

The untyped nature of thera tree makes it ideal place to handle generic editing functions, that have to be consistent for all scene graph nodes - undo, redo, cut, copy, paste, load and save. The invariant in Khayyam document system is, that the properties of Miletos::Object are determined only by the attributes and children of Thera::Node. So restoring the Thera::Node properties to previous value, also restores scene graph to previous state.
Thera::Node has very few properties, so to implement undo and redo, we have to only record 5 different types of mutation events (attribute change, content change, child insertion, child removal and child relocation). This is managed by Thera::Document container.

For each mutation event, a new record is appended in document undo list.

For attribute changes keep node location, key and old value
For content changes keep node location and old content
For child insertion keep the location of new node
For child deletion keep the copy of child node and it's previous location
For child relocation keep the old and new locations of child

Undo works by rolling back the record, and moving it from the top of undo list to the top of redo list.

Transaction logging can be turned on and off. Normally it has to be always on for editable document, but in certain cases - like during ensuring unique id attributes to all objects during document creation, it is turned off (id uniqueness is required feature, so this procedure cannot be undone).
In addition to transaction logging, there is transaction collation. If this is turned on, subsequent changes of the same attribute do not create new records, but only update the last record. It is used for tracking continuous numerical attribute changes - like the ones controlled by spinbutton or slider.

Similarly cut, copy and paste are implemented by storing the clone of copied node(s). During paste, the clone is re-cloned into document tree - and libmiletos objects will be built and updated automatically by event listeners.

Some concerns

While the untyped nature of thera tree makes editing functions simple and consistent throughout document, it has one drawback. As objects are often referenced by id values, and id has to be unique in document, copying reference pair does not work as intended. The id of new referee will be changed to some unique value, but the referencing attribute of referer will be not. So the referer will link back to the original object, instead of the new object.
I have some ideas, how to handle it - by keeping a dictionary of id overwrites during libmiletos object building phase, but at moment it has to be adjusted by hand.

Also, as libthera keeps all values as text, updating parsing these may take more time than is reasonable to spend during interactive editing. To dealt with this, many interactive functions work in two-stage way.

When input is grabbed (mouse button pressed), the initial state of object is recorded
During editing (normally dragging) libthera is skipped and editing function applied directly to scene graph nodes
When editing is finished, the last state is written to libthera
If editing is canceled, object state is read back from libthera (which has the initial value)

Thus interactive functions do not constantly update text attributes, but instead the state of scene nodes directly. As an extra bonus the single editing action (click-drag-release) is recorded as single document transaction, because the libthera values are updated only during release.

That's all for now. Libthera can be donwloaded as part of khayyam source from SourceForge page. Or the latest version can be fetched from Sodipodi SVN:

https://sodipodi.svn.sourceforge.net/svnroot/sodipodi/trunk/thera

Have fun!

How to use Poser/DAZ models in Khayyam

2011-03-12T20:28:00.000+02:00

There is almost endless number of Poser models and props (accessories) available from sites like DAZ3D, Renderosity and Renderotica (adult content). It is possible, although somewhat tricky, to get many of these to work in Khayyam. So I have composed a small tutorial of loading figures, hair, clothes and materials in Khayyam.

Warning: Khayyam is still in very early stages of development and many models do not work. So better do not purchase expensive models unless you also have Poser/DAZ or know, that you can get them working. But you can always hunt for cheap things, bargains and free stuff (DAZ forums is a great resource for finding free models). If something does not work, I can usually fix the Khayyam code - but you have to buy given model for me so I can experiment :D

1. Loading Cr2 model

Cr2 (Character Rig) is the skeletally controlled model, that is mostly used for human figures (also animals) and more complex hairstyles.
Select Object -> Import -> Import Poser mesh
Depending on your library size it may take some time to load all previews. When done, the import dialog will open. If you have not specified Poser library path yet, the library list is empty. Click on Choose Library and select the Runtime directory of your model installation tree.
Most human figures are under Character subtree. I use DAZ People -> Victoria 4.2.cr2 as an example for the tutorial.

Khayyam Cr2 import dialog with Victoria 4.2 selected

Click Import and the the import options dialog will open.

If importing main figure you should keep all options at default values, as shown above.

Create skeleton will build editable skeleton for rigged model. Normally you want to keep this checked.
Import as standalone mesh will build new toplevel figure. Unless you are adding hair or clothes to existing figure, this should also be checked.

Click Import and the figure will be inserted to main document. You can close the Import Poser dialog or keep it open, as we will use the same dialog later again.

Figure imported to main document

As you can see, the default look is quite plain. We'll add proper materials soon to make her more attractive.
Now it is time to open the Document Tree dialog, if not already open. Select the figure (click on it, so the selection box turns orange) and choose Dialogs -> Document Tree.

Document Tree dialog with some nodes expanded

At the left side is the DOM tree of current document. At the right side are the property pages of the currently selected node. Most fine-tuning of objects is done with property pages.

All poseable objects have toplevel node Figure. It works as a container of one or more geometries (actual poseable objects), skeleton (a controller of those geometries) and possibly other node types.
Selecting the single geometry under imported figure opens the property page of Cr2 object. Here you can see a tree of actors and associated dials. The base V4 figure has only few morphs, but if you expand the tree and select head actor, you can access the lip sync dials, for example.

Khayyam build IK Chains automatically from model data - but does not set bone constraints. You can play with IK chains (and FK posing too) by selecting bone edit mode in main window.

NB! V4 figure has extra EyeBrow object, that partially covers the face. To turn this off, select the geometry node in document tree, select the middle Geometry property page from the notebook at right, scroll down and turn the visible checkbox off for 1_EyeBrow material.

2. Adding clothes

Clothes have to follow body position, so they are also poseable objects (of type cr2). To import clothing item, keep the main figure selected and open again Import Poser Dialog (or bring it up, if you did not close it). Select proper clothing item (it should appear in preview, if Khayyam can load it) and click Import. Unfortunately the free V4 base does not include clothes, so you have to buy these yourself or search for free ones. I am using free Bucketload 3D Sunny Bikini for current tutorial.

If you had the figure selected, the import options dialog has a bit different set of controls selected. Normally you want to keep the preselected values.

Create skeleton is unselected, because the figure already has skeleton.
Skin of selected mesh - it means, that it will be fully controlled by main figure skeleton.
Parent bone and anchor bone are set to the lowest common bone (actor) in the hierarchies of both objects.

Click Import and clothing item should be added to the figure.
NB! If the clothing item is built for a different base figure (V3, A3...) it is quite possible, that it does not "fit". Sometimes you can adjust it with morphs, but often this does not help. You can remove wrong objects by selecting corresponding geometries in document tree and clicking on trashcan image.
Repeat clothing import for as many items as you need (well - you do not need any, but to keep this tutorial work-safe, I'll add at least bra and panties).

V4 figure with bikinis loaded

As you can see, both the main figure and bikini are plain. We'll set material as the next step.

3. Loading materials

Predefined materials are either Pose files (pz2) or Material definition files (mc6). It is also possible to set materials by specifying texture files directly, but I'll skip this at moment (the procedure is the same, as in SBZ tutorial).
Materials are applied to geometry nodes - not the full figure. So in Document Tree Dialog, select the body geometry. On the property page, click the button Load Material...
Materials are usually either under the Pose (older version) or Material (newer) subsection of library tree. You have to select correct material type - the ones for wrong object (clothes vs. body) do not work.

Library tree with material file selected

Click OK, and material will be imported. Usually the textures are huge, so depending on the speed of you computer and GPU it may take some time.
Material definitions are added as Pose nodes under Geometry nodes. There can be many material definitions - they are parsed from bottom to top - so it is, for example, possible to add makeup on top of body materials. To delete material definition, simply delete corresponding Pose node.
Repeat the same procedure for clothes - first select clothing geometry node and then click Load Material... (of course you have to select appropriate material file for clothing).

4. Adding hair

There are 2 types of hair - poseable (cr2) and prop (hr2).
Adding cr2 hair is exactly the same as adding clothes - select main figure, choose hair object in Import Poser Dialog and import it as skin of selected mesh. Apply material just like for clothes.
Hr2 meshes do not have skeleton, thus they are imported as Poseable elements. Usually short hair is hr2, as it simply follows the movement of the head and does care about the neck and shoulders. But this will be shown in the next tutorial.

V4, bikinis and hair with materials applied

And this is it.
The next time I'll show, how to load poses, inject morphs and import Hr2 hair. Or you can try this yourself - it is not complicated at all, once you find the right place in document tree :D

Have fun!

Snapshot release 20110310

2011-03-10T16:52:00.000+02:00

A new snapshot release 20110310 is available from SourceForge page as source tarball and precompiled Win32 binary.

Fixed PNG export gamma so Pov-Ray rendered images have similar tone to screen
Directional lights now cast shadows
Fixed Poser cr2 joint order and pose loading
Support for Yuusha models
BVH export allows one to manually specify root bone

Also Sara-chan (included as demo model) got a little update - better face topology, cuter and more realistic mouth and thicker hair.

Sara Tween Girl version 1.1 (Blender render)

Included model has IK chains and constraints, so it can be used as a reference, how to set up these for other figures. Until I'll get time to write tutorial about it.

A new face topology of Sara-chan in Blender

Have fun!

Where to find free 3D models?

2011-03-01T22:56:00.000+02:00

Even if it works for you, Khayyam is only as good as the 3D models you can insert into your scene. Thus I put together a small list of useful and/or interesting sites where you can find free or cheap 3D models. It does not pretend to be some sort of top 8 - there are many-many more websites, so you are free to suggest more.

A discus and neon tetras from Toucan Virtual Museum, rendered with POV-Ray

The places to go for models (in no particular order).

1. TurboSquid
This is probably the biggest resource of user-submitted 3D models in Internet, ranging from free or cheap class works to very professional and expensive characters and architectural models.

2. DAZ 3D
DAZ is the creator of both the professional 3D applications and the base human characters for Poser/DAZ Studio (Victoria, Michael and various derivatives). They have online store with lots of high quality models, some of them available for free (require registration still), including the starter versions of most of their human characters.

3. DAZ 3D forums
They have special sections for advertising free models. From there you can find links to some free hair and clothes to complement your figures.

4. Renderosity
For many this is The Internet Marketplace for 3D art. Huge amount of models for Poser/DAZ including many free ones. The prices seem to be a bit cheaper than in DAZ store. Registration required.

5. Toucan Virtual Museum
A small site that has some very nice free fish, flower and insect models, that are hard to find otherwise.

6. Archive 3D
More than 20 000 architectural models (mostly furniture) available fro download. No registration required.

7. Google 3D Warehouse
The companion site to Google SketchUp free modeling program. Big and growing selection of free user-created models.

8 Renderotica (Warning: Adult Content)
A must be site, if you want to render some steamy action. No free models, but otherwise good selection of characters, poses and accessories.

I have not tested them all, so I cannot tell, how much Khayyam compatible model formats are there.

Have fun! And do not forget to support the creators by purchase, donation or advertisement, if you find their models useful for you!

The Girl and full body morphs

2011-02-27T02:34:00.000+02:00

Have spent last days by writing code for morph injection. While Khayyam has supported both standalone and ERC morphs for some time, they had until now to be specified in the main cr2 file.

ERC stands for "Enhanced Remote Control" and it is a feature of Poser/DAZ Studio to chain morphs (actually arbitrary channels) together, so changing the value of master dial propagates to different body parts by changing their channel values. Thus, for example, applying FBM (Full Body Morph) of The Girl, the master dial applies corresponding morph to head and at the same time moves eyes to slightly up and wider. Plus many-many things to other body parts.

The ERC feature is used extensively in DAZ version 4 figures (Victoria, Michael, Aiko, The Girl). Actually Aiko and The Girl do not have separate bodies at all anymore, but are defined as FBMs of Victoria. Most recent clothes have conforming morphs as well, but unlike the morphs of base figures they may be needed to be loaded manually from separate file. Thus the urgent need for Khayyam for applying extra morph files to objects (by poser slang it is called injection).

The result can be seen at the following screenshot:

The Girl at the beach

Here you can see The Girl (Victoria 4 morph, so the body is actually the same as on previous Victoria pictures). Material is the original DAZ Studio "The Girl" texture set. Swimwear is Bucketload Sunny Bikini set, morphed to The Girl body. Background is beach scene from Sexy Beach 3.

Not everything works yet - for example The Girl FBM changes the sizes of some body parts like palms, and scaling is not implemented properly in Khayyam. To get the correct scaled hands, skeleton has to be modified (to move fingers along with scaled palm). Plus SmoothScale channel is not used, so the scaling boundaries are sharp.

New snapshot release 20110222

2011-02-23T13:21:00.000+02:00

A new snapshot release 20110214 is available from Sourceforge page as both source tarball and precompiled Win32 binary.

Fixed Poser deformation spheres so there are no "vertices going wild" anymore
Materials can be imported as full sets from PZ2 files
Poses can be applied to skeleton prom PZ2 files
Transparency channel is applied automatically to Poser materials
A new code for figure welding. As a result Chibibel is not broken anymore, but most body morphs do not work properly

And an obligatory screenshot - this time Chibibel was exercising in morning forest - but she is a bit worried by all you voyeurs.

Chibibel in forest demonstrating imported Pz2 pose

Many things are still missing, but overall the program is taking shape nicely. So give it a try, if you have some unused models lying around and let me know about your mileage.

Poses, poses, poses

2011-02-23T01:21:00.000+02:00

Poser file formats are wonderful (or terrible) patchwork of figures and properties, endlessly extensible through a procedure called pose or morph injection. Basically you will take base figure (or extended one), add custom morphs, poses, materials and accessories (props), call it with fancy name and sell the extensions separately. As a result there is big and lively ecosystem of modelers and artists making living by selling virtual things for virtual worlds.

I am currently halfway through the implementation of those extension mechanisms for Khayyam. The most important ones - materials and poses mostly work now in CVS version and the results are really worth seeing.

Normally you start from plain base figure. As an example I use here the most famous one - DAZ Victoria 4 freely available from DAZ webpage.

Victoria 4 base figure

Not very pretty - right?
Next let's load a predefined pose to make it a bit more lifelike.

Victoria 4 posed

A bit better, but still ugly.
Now we import custom materials.

Materials, swimwear and hair

Most texture sets are a bit ... realistic, so I added swimwear as well. Also imported hair. Imported objects are usually immediately skinnable - i.e. they follow the figure pose automatically, as you can see from swimwear.
There is more Khayyam can already do - like apply morphs.

Closeup of face with eyes targeted and mouth morphed

Materials can be applied one on top of another - like eye color or makeup separately from main body texture. Transparent hair is a bit messed up in Khayyam, but will render properly if exported.
And last a quick render of the same figure with POV-Ray (different hair material and pose):

Victoria 4 at beach - renderd with POV-Ray

That's all for today. Expect a release soon ;-)

Converting rotation matrix to arbitrarily ordered Euler angles

2011-02-18T00:22:00.002+02:00

There is enhanced version of this algorithm available in new post.

The Matrix and Quaternion FAQ presents the straightforward method of converting rotation matrix to Euler angles. Still, it has two shortcomings.

There is discontinuity close to Z rotation of 90 degrees, where X and Y rotations suddenly jump from close to zero to close to 180 degrees.
It only shows the way to get angles in XYZ order (i.e. M = Mx * My * Mz).

Arbitrarily ordered angles are extremely useful for skeletal animation to give joints more natural deformations. But the main motivation was actually writing libmiletos container for Poser figures (cr2 file format). These have always bone rotations in twist/bend/bend order, while twist is defined as the rotation of the main axis of the bone. And as Poser figures have different bending algorithms for different rotations, the angles cannot be easily reordered.
So I have written slightly enhanced version for libelea.

Stable decomposition of matrix to Euler angles

First the original code.
It is derived from expanded form of rotation matrix:

|  CE      -CF       D   0 |
M = |  BDE+AF  -BDF+AE  -BC  0 |
    | -ADE+BF   ADF+BE   AC  0 |
    |  0        0        0   1 |

A,B are the cosine and sine of the X-axis rotation axis,
C,D are the cosine and sine of the Y-axis rotation axis,
E,F are the cosine and sine of the Z-axis rotation axis.

From it the following algorithm can be derived (using row-major matrix layout, so it has to be transposed for column-major OpenGL matrices):

angleY = asin (m[2]);
C =  cos (angleY);
if (fabs (C) > 0.005) {
    trx    =  m[10] / C;
    try    = -m[6]  / C;
    angleX = atan2 (try, trx);
    trx    =  m[0] / C;
    try    = -m[1] / C;
    angleZ = atan2 (try, trx);
} else {
    angleX = 0;
    trx    =  m[5];
    try    =  m[4];
    angleZ = atan2 (try, trx);
}

The problem is that when angleY goes from slightly below 90 degrees to slightly above 90 degrees, C changes sign and suddenly angles X and Y jump to different quadrant.

The enhanced version from libelea (also written for row-major order matrices):

aY = asin (m[2]);
aY2 = M_PI_F - aY;
if (fabs (m[2]) != 1) {
    C = cos (aY);
    C2 = cos (aY2);
    trX = m[10] / C;
    trY = -m[6] / C;
    aX = atan2 (trY, trX);
    aX2 = atan2 (-m[6] / C2, m[10] / C2);
    trX = m[0] / C;
    trY = -m[1] / C;
    aZ = atan2 (trY, trX);
    aZ2 = atan2 (-m[1] / C2, m[0] / C2);
} else {
    aX = aX2 = 0;
    trX = m[5];
    trY = m[4];
    aZ = aZ2 = atan2 (trY, trX);
}
if ((aX * aX + aY * aY + aZ * aZ) < (aX2 * aX2 + aY2 * aY2 + aZ2 * aZ2)) {
    angleX = aX;
    angleY = aY;
    angleZ = aZ;
} else {
    angleX = aX2;
    angleY = aY2;
    angleZ = aZ2;
}

The only trick here is to calculate both Y angles satisfying the formula

sin (aY) = c[2]

and subsequently two versions of other angles too. Then the actual set of angles is chosen such, that the squared sum of all angles is lesser. This behaves extremely well as far as I have tested it.

Decomposition of matrix to arbitrarily ordered Euler angles

The code from libelea (matrices are again row-major order).
The order of axes is given as an array of 3 integers, whose values denote axes (i.e. {0,1,2} is XYZ, {1,0,2} is YXZ and so on.

// We need either quaternion or axis/angle pair
// of given rotation
// Go for quaternion now
Quaternionf q = m.getRotationQuaternion ();
float sign =
    ((order[1] == (order[0] + 1)) ||
     (order[2] == (order[1] + 1))) ? 1.0f : -1.0f;
// Array of identity axis vectors
static Vector3f iv[] = {
    Vector3fX, Vector3fY, Vector3fZ
};
// Compose matrix that transforms to reordered axes space
Matrix3x4f s;
for (int row = 0; row < 3; row++) {
    for (int col = 0; col < 3; col++) {
        s[4 * row + col] = iv[order[row]][col];
    }
}
for (int col = 0; col < 3; col++) {
    s[8 + col] = sign * s[8 + col];
}
// Transform quaternion
// As we transform the first 3 values anyways,
// we can as well use vector transformation method here
s.transformVector3InPlace (q);
// Compose new rotation matrix from transformed quaternion
Matrix3x4f rs;
rs.setRotation (q);
// Decompose new matrix to Euler angles
rs.getEulerAngles (angles);
// We have to switch sign, if order was left-hand
angles[2] *= sign;

The idea is to transform matrix in such way, that the reordered rotation axes of original matrix become XYZ rotation axes of transformed matrix and then perform trivial decomposition.

Have fun!

Valentine day release

2011-02-15T00:06:00.002+02:00

A new snapshot release 20110214 is available from Sourceforge page as both source tarball and precompiled Win32 binary.
This time it is mostly about Poser/DAZ 3D file format support.

Most joint properties work (there are slight inconsistencies with deformer spheres still)
Body morphs kinda work, but the results may vary depending on model and morph
Hair can be imported as poseable item (attached to head actor)
Textures can include separate transparency maps
Clothes can be attached as skins so they follow poses

Not everything is easily available from GUI yet, so property editor is must-be tool.

DAZ Victoria 4 posed in Khayyam and rendered with POV-Ray

I have tested it mostly with Victoria 4 and Chibibel, so there can still be inconsistencies with other models. Victorial is the DAZ 3D base female model and freely available at moment. Chibibel used to be free also, but the promotion is over now.
Other than Poser file formats (cr2, pp2 and hr2), there are improvements in Collada file exporter, OBJ importer skeleton editor. Plus small bugfixes here and there.

How to get quaternion from rotation matrix

2011-02-13T00:23:00.001+02:00

For now probably the whole generation of programmers has learned the basics of projective geometry from the famous Matrix and Quaternion FAQ. I myself have consulted it numerous times while writing Khayyam (or more precisely Elea support library). But experimenting with the 3D transformations I found that while theoretically correct, the two most esoteric methods of the FAQ give suboptimal results. Namely - converting the rotation matrix to quaternion or Euler angles becomes unstable for certain rotations and - at least for Euler angles - does not give the most intuitive solution. So decided to write slightly enhanced variants.

The original code from FAQ:

T = 1 + mat[0] + mat[5] + mat[10]
if ( T > 0.00000001 ) {
    S = sqrt(T) * 2;
    X = ( mat[9] - mat[6] ) / S;
    Y = ( mat[2] - mat[8] ) / S;
    Z = ( mat[4] - mat[1] ) / S;
    W = 0.25 * S;
} if ( mat[0] > mat[5] && mat[0] > mat[10] ) {
    S = sqrt( 1.0 + mat[0] - mat[5] - mat[10] ) * 2;
    X = 0.25 * S;
    Y = (mat[4] + mat[1] ) / S;
    Z = (mat[2] + mat[8] ) / S;
    W = (mat[9] - mat[6] ) / S;
} else if ( mat[5] > mat[10] ) {
    S = sqrt( 1.0 + mat[5] - mat[0] - mat[10] ) * 2;
    X = (mat[4] + mat[1] ) / S;
    Y = 0.25 * S;
    Z = (mat[9] + mat[6] ) / S;
    W = (mat[2] - mat[8] ) / S;
} else {
    S = sqrt( 1.0 + mat[10] - mat[0] - mat[5] ) * 2;
    X = (mat[2] + mat[8] ) / S;
    Y = (mat[9] + mat[6] ) / S;
    Z = 0.25 * S;
    W = (mat[4] - mat[1] ) / S;
}

The problem lies in how the calculation method is switched, depending on the comparison of certain matrix elements. If, for two sequential rotations, the matrix values happen to be only slightly different, but fall into different calculation paths, the resulting quaternions will be very different and thus interpolating between them results in sudden twists. This should not happen, if your matrices are perfectly orthogonal - but if they come into existence as the result of many multiplications and (especially) inversions chances are good that they are not. Now add into the mix rotation angles close to 180 degrees, and the there will be distortions.

Stable variant from libelea (please notice, that while usually libelea has column-major order, packed 3x4 matrices, as used here, have row-major order. So to port the code to OpenGL matrices you have to transpose matrix):

/* Get normalized transformed unit vectors of rotated space */
Vector3f axx(Vector3f(m[0], m[4], m[8]).normalize ());
Vector3f axy(Vector3f(m[1], m[5], m[9]).normalize ());
Vector3f axz(Vector3f(m[2], m[6], m[10]).normalize ());

/* Calculate transposition vectors */
/* I.e. how the unit vector endpoints will be transformed */
Vector3f tx = axx - Vector3fX;
Vector3f ty = axy - Vector3fY;
Vector3f tz = axz - Vector3fZ;

/* Find two biggest transpositions */
f32 txl2 = tx.length2 ();
f32 tyl2 = ty.length2 ();
f32 tzl2 = tz.length2 ();
Vector3f *a = &tx;
Vector3f *b = &ty;
if ((txl2 < tyl2) && (txl2 < tzl2)) {
    a = &ty;
    b = &tz;
} else if ((tyl2 < txl2) && (tyl2 < tzl2)) {
    a = &tz;
    b = &tx;
}

/* Get axis (cross product of two biggest transpositions)*/
Vector3f ax(*a * *b);
if (!ax.length2 ()) {
    /* Zero rotation */
    return Quaternionf0;
}
ax.normalizeSelf ();

/* Get vector perpendicular to axis and transform it */
Vector3f s(a->normalize ());
Vector3f t(m.transformVector3 (s));
t.normalizeSelf ();

/* Find rotation angle (between vector and its transform) */
Vector3f s_t(s * t);
f32 e = Vector3f::scalarProduct (s_t, ax);
if (e < 0) {
    ax = -ax;
}
f32 theta = Vector3f::angle (s, t);
f32 sint2 = sinf (theta / 2);
f32 cost2 = cosf (theta / 2);
return Quaternionf(ax[X] * sint2, ax[Y] * sint2, ax[Z] * sint2, cost2);

The idea is, that any vector perpendicular to axis will be transformed to vector also perpendicular to axis. So we can get axis as the cross product between such vector and its transform.
Now, as you can see, this is much slower, involving the vector normalization, cross products and trigonometric functions. But hopefully you do not have to do this very often - I mostly only needed it for importing foreign animation formats and compacting rotation matrices for serializing.
I have used this method quite extensively and it has excellent stability.

Next time I'll show, how to avoid sudden instabilities if converting rotation matrix to Euler angles.

DAZ Victoria 4

2011-02-10T01:51:00.000+02:00

Have been trying to get DAZ 3D base model Victoria 4 to load and render in Khayyam. Things are slowly getting better, although it is not in very usable state yet.

In-engine screenshot of Victoria 4 with Jamie hair

Body is loaded normally and most joints behave well
Morphs do not work yet
Hair can be loaded only as static object (no morphing, not attached to skeleton)
Textures can be applied (only diffuse, specular and transparency)

With some patience it can be made looking pretty good. Like most Poser models, the textures are either missing from base model, or so ugly they are pretty useless. So one has to apply textures one-by-one, using material overrides.

POV-Ray rendering of Victoria 4 with Jamie hair

Getting Poser stuff to work is pretty high-priority now. Especially because Illusion does not seem to be planning to release anything noteworthy for some time. Meanwhile at places like Renderosity there is almost infinite amount of very high quality content available - although most of it is a bit too realistic for my taste.

Sara and Cyberdemon (and lighting)

2011-02-07T00:09:00.000+02:00

I have been ill (sick if you are American) for the last week, so there was very little interesting things happening with Khayyam. But at last I am feeling better now, so hopefully more will come.

I took few evenings some weeks ago and fixed diffuse and specular lighting (and tangent map calculation). As as result, there is again a reason to read normal- and specular map textures for objects.

Sara does not surrender easily (of course AK-47 itself is also legendary)

At least Doom creatures will look much better this way. Unfortunately Illusion games do not use normal maps, so there are no visible enhancements - unless you want to emulate the in-game plastic oily look.

But - it is possible to replace textures on Illusion (and other formats too) models with materialDNS node (look at tutorial for how exactly) - and this material node supports both normal and specular maps. So if someone wants to experiment, surface effects can be done with some effort.

There are still some big things to do for lighting - like cascading shadow maps, shadows for point and parallel lights and so on. Although immediately I want to play with skin shader instead...

Snapshot release 20110130

2011-01-30T18:50:00.001+02:00

I have made a snapshot release of the latest development tree as of 2011/01/30. This time there are both source tarball and precompiled Win32 binaries.
It can be found from SourceForge project page, or use direct download links:

What is new (compared to 4th of January release)?

OBJ and 3DS importers (static objects)
OBJ exporter
Fixed Collada importer/exporter (works with Blender 2.5)
Preliminary IK solver for skeleton posing
Bone constraints for IK solver
Object library with thumbnails to save useful models

Basically the available list of models increased dramatically. There are literally hundreds of different sources of free or cheap 3D models in OBJ and 3DS formats.

Bonus model

As a extra bonus, Sara tween girl Collada model is included in release (in both versions).


Sara tween girl, Blender model

The Blender source file can be downloaded from TurboSquid.

Mini-tutorials

I have previously written two mini tutorials, both available from this site. In case you missed these, they can be found at:

Have fun!
Lauris Kaplinski

Rendering with POV-Ray

2011-01-30T01:54:00.001+02:00

POV-Ray (The Persistence of Vision Raytracer) is high quality free raytracing renderer. Khayyam can export most models and scenes into POV-Ray file format (.pov) to allow special effects, like focal blur, global illumination and so on. Following is a mini-tutorial for scene composing and exporting.

1. Build your scene

This is really outside of this tutorial so only few hints.

As the first thing, open Document Tree editor (Dialogs -> Document Tree). It has property pages for the most of object types in scenes and most fine-tuning has to be done with it.

Add lights. It can be done later, but a good idea is to add at least one directional light as the first step (Objects -> Add -> Lights -> Directional Light) because otherwise model will look plain and it is hard to understand their poses exactly.

Import objects and figures (Objects -> Import). Currently there is support for most Illusion model formats (althoughthe ones from cell-shaded games do no look nice), MD5 (Doom3 and Quake4), OBJ, 3DS, Collada (partial) and Poser (partial) file formats.

Scale models. Default scales are mostly OK for Illusion, MD5 and Poser files, but the ones imported from other formats may be of very different scales. For scaling, select object (click on it when it has yellow highlight box) - the highlight box should turn orange. Now look at Document Tree dialog - either object of type Figure (poseable object) or StaticMesh (non-poseable) should be selected.

Document tree showing selected figure

Figure and StaticMesh are toplevel containers that can include many geometries (body, hair, clothes...). Select one geometry node in tree and the content of the rightmost notebook pane should change. Each notebook page corresponds to one level in selected object type hierarchy so switching pages gives you different levels of controls.

Click on Geometry tab and there are controls applicable to all Geometry types, among others a scale spinner.

Document tree with SkinnedGeometry selected Geometry property page open

Place models. For this select model and transform control should appear. If it is not visible, try pressing Q key for few times - it cycles the control placement between object origin, object bounding box and the center of screen. Pressing SPACE key toggles between move and rotation controls. The same can be achieved with clicking on already selected model.

Take a look at hotkeys list (Help -> Hotkeys) - there are some useful keyboard and mouse hotkeys, like hiding controls temporarily and so on.

Pose figures - to do this, select figure (poseable object, like Illusion character, MD5 or Collada model) and choose skeleton tool from toolbar. If the selected object is of figure type, bluish skeleton should appear. Nothing will happen, if the object is not of posebale type.

Selected object with skeleton control

Posing individual bones is quite similar to placing objects - although normally you do not want to move bones (it breaks body very unnaturally) but only rotate them.

Save scene. Save often, as Khayyam is still alpha and crashes a lot.

2. Set up lighting

Special lighting is the main reason you want to raytrace your scene. So take some time and try to set up lighting as well as possible - it really makes difference in final images.
Add spotlights (Objects -> Add -> Lights -> Spotlight). There can be practically unlimited number of spotlights, but they make rendering slower. Also semitransparent objects (hair) cannot currently be lighted by more than four spotlights.
Set light direction for spotlights. The easiest method to do this, is copying light direction from camera.

Move camera to show the scene light you want it to be seen from the spotlight.
From document tree select SpotLight node
From right pane select Light tab
Click From Camera button
From the same place you can set the light intensity and color

Document tree with Spotlight selected and Light property page open

Ambient lighting adds undirectional light to the whole scene. It can be used to make shadow regions to have less contrast - but it tends to make scene plain.
Diffuse lighting determines the actual spotlight intensity and color.
Direct lighting if for specular highlights, but at moment it does not work reliably.

If you want to add light with soft shadows, use Area Lights. They are similar to spotlights, but are composed of many small lights on rectangular grid. Consequently they can slow down rendering quite a lot, so by default they only have 2 x 2 nodes. To achieve softer effect, you can add more sublights from document tree dialog.

3. Export scene to POV-Ray format

To export POV-Ray scene, select File -> Export POV-Ray Scene...

POV-Ray export dialog

The exporter dialog has three tabs. Normally you want to start from default values, as these render reasonably fast and you can check how the scene looks like. Khayyam and POV-Ray use slightly different lighting formula (actually very different if you use radiosity) so you may want to adjust light intensities and colors before doing final render.

If you have exported scene once and have not added any new objects to it, you can uncheck Export Textures as PNG files checkbox - this saves some exporter time, as it does not have to write texture files over and over.


Lighting properties from POV-Ray export dialog

If you are otherwise content with the scene lookout, you can enable Radiosity. This add indirect lighting to objects - i.e. light bouncing back and forth from surfaces and thus makes the sene much more natural. But it makes rendering considerably slower and can mess up lighting, as in Khayyam you cannot estimate easily, how much reflecting light changes the overall scene brightness - so experiment.

Camera properties from POV-Ray export dialog

Adding Aperture makes objects out of focus (nearer and further) slightly blurred - how much, depends on aperture value (smaller value reduces blur). The focus point is determined by the rotation center in Khayyam (fading target image that appears if you move camera) so place it close to the objects or features you want to make sharp.
Aperture makes rendered images much more photo-like and can add a lot to the mood. But it makes rendering slower.

Click Export and save file with the extension .pov. If you have already installed POV-Ray, it has registered itself as default handler for those file types.

4. Render it with POV-Ray

Using POV-Ray is outside this tutorial. Some hints though:

POV-Ray opens all files in builtin editor, so to make small changes you do not have to re-export scene again.
Rendering starts with button Run
You can select render size from top-left menu box
Render result will automatically be saved as png file to the same directory as pov file.
POV-Ray uses custom scene description language that can be quite complex to understand.

Fully set up scene in Khayyam

The same scene rendered with POV-Ray (using radiosity and aperture). As you can see, using radiosity added lot of extra light to environment.

And this is it! Have fun!

Sara

2011-01-21T18:57:00.000+02:00

I have for long time planned to bundle some freeware models with Khayyam. Now, at last, the first iteration of Sara - a young female - is nearing completion. She is quite low-poly, so she will be better suited for real-time animation than for renders.

Sara rigged in Blender

She still needs hair and some more clothes before making a public debut.

Experimenting with IK solver

2011-01-02T21:31:00.000+02:00

Happy new year everyone!

I have spent most of my free time between Christmas and New Year by moving the preliminary IK solver code from animation merge to generic pose editor. The results are mostly working, so expect a release sometimes soon.

Inverse kinematics is a set of algorithms everyone is talking about, but there is actually very little useful information found in web. Other than studying the source code of existing software, that is. There are actually two complexities - first the algorithm itself and then specifying meaningful constraints. Plus all kinds of small technical things.

The algorithm is an easier part. Just went with Downhill Simplex, mainly because it is conceptually easy and reasonably fast. The function is simply the distance between IK target and the predefined endpoint of moving limb.

Constraints are trickier. We have to add the properly scaled tensions of joints to distance function, so joints try to find the easiest (most relaxed) position for given target. As much as I hate Euler angles, I cannot imagine quick and easy way to specify joint tension using only quaternions and/or matrices. It should be possible to create 3-dimensional grid of values and interpolate normalized quaternion in that space. But I do not want to experiment with it before I can get everything working simpler way.
So what had to be done was to decompose all bone relative movements (compared to rest position) into Euler angles. The order of axes is configurable (XYZ, XZY and so on).

Once we have Euler angles, it is quite logical to specify the maximum positive and negative rotations allowed to given bone. But there is one caveat - minimization algorithms normally require the tension function to be smooth. So we cannot simply clip the tension function at threshold. Also it is normally not a good idea to keep the tension value constant below threshold, because joints always prefer to be as close to rest position as possible.
At moment I made a mix of two power functions for tension calculation:

T = R * (angle / P) ** 1.25 + (angle / P) ** 16

T - calculated tension value
R - rigidity (0-1) of the movement
P - threshold value (maximum rotation)

There are two different set of threshold and rigidity values - one for positive, one for negative values. Rigidity determines, how fast the tension increases below the threshold value (it has small exponent 1.25 to make the overall function differentiable at zero).

The example of tension function

Here is a graph of example tension function with parameters -1.0;1.0 (negative) and 1.5;0.1 (positive). It describes a joint, that moves backwards up to about one radian with considerable tension and forward up to 1.5 radians relatively freely. Although it does not seem so looking at graph, the function is actually smooth at zero.
Certain joints have some rotations blocked - like twisting and sideways bending for knees. This is better done by turning those axes off completely instead of setting very small movement thresholds, because we want to keep the degrees of freedom as low as possible.

And it works - at least wee enough for static positioning. For some reason the simplex solver diverges a lot for small changes in target position if the overall movement is relatively big.

Positioning of limbs with IK targets

The latest version of Khayyam has a set of meaningful IK chains and rotation constraints built into XPP importer (only for SBZ and compatible skeletons).

How to teach Imp to dance

2010-12-27T20:06:00.001+02:00

A new video showing how to import Characolle dancing animation to SBZ figure, then export it to BioVision (bvh) file and then apply to Doom 3 Imp model (md5).

To be precise, the merged animation cannot be saved yet, expect more to come...

Importing Sexy Beach Zero figures

2010-12-22T16:41:00.002+02:00

Current windows build of Khayyam can be downloaded from Floyd Sourceforge page.

Here is quick tutorial how to import SBZ figures. The similar procedure can be used for other multi-part meshes (SB3, School Mate etc) - but not all collection formats have working autodetection for textures, bones and so on.
From main menu select: Objects -> Import -> Import Xpp Mesh

Click "Choose directory..." and select the "data" subdirectory in installed game location.
At the right-left is the list of all collection files (.pp) in chosen location. For SBZ, the bodies are in file sb03_00.pp. The game format should be autodetected from file name, but if it fails, select "Sexy Beach Zero" manually from game dropdown list. After selecting correct collection file the contents of it should appear in lower-left list.
Female bodies are named cw_body_??_??.xx.
Keep "Hide extras" and "External textures" checked for now - these make oiling/massage guide mesh invisible and replace plain skin materials from predefined textures.
Select proper body model and the preview should appear at right. The common camera controls (middle and right drag) work similar way to the main window.
Click "Import". The import options dialog should appear.

If you are importing the first object, the only available option is "Import as standalone mesh". Keep "Create skeleton" checked if you want to pose the figure later. Click "Import".
Imported body appears in main window. But as there is no proper lighting, it looks plain.
Select "Object->Add->Directional Light" to make it better.

Select body by moving mouse over it (yellow highlight box should appear) and clicking. Selection is marked by orange wireframe around the body.
Now you are ready to import head. Again chose "Object->Import->Import Xpp mesh..."
From the collection list select the same collection, chose any of the head files (cw_head_??_??.xx) and click import.

The proper import options should be preselected. You have to import it as "Skin of selected mesh" so it will be controlled by the same skeleton. "Parent bone" and "Anchor bone" determine, which bones will be merged between existing body and new head skeletons. Click "Import" and voila - body has now head.
Repeat the same procedure with hair (the name of mesh is cw_hair_??_??.xx).

The next step is applying a texture to swimwear. For this we use builtin DOM editor - the most powerful tool of Khayyam.
Choose "Dialogs->Document Tree".
Expand "Scene" and then "Figure" nodes from left-hand tree view. Figure is a poseable object, that can have multiple skins (body, head, clothes) controlled by the single skeleton and additional poseable objects (like items at hand). The imported SBZ meshes are "GeometryXX" nodes. Select the first one of them (the body mesh).

At the right side there are tabs for the selected node and its parent classes. At moment we are interested in the Xpp geometry node itself (GeometryXX). You can see the list of all used internal materials, with visiblity checkboxes and optional external material ids. Importer autodetection should have made oiling guides invisible already. The body materials should have external textures attached (materialDNS_6 and materialDNS_5).
Select bra material mn_mizugi_00_00. From dropdown box below select "Create new" and click "Apply". This creates new texture override node for bra and opens material editor to define texture for it.
Texture editor looks like similar to Xpp mesh importer. First click "Choose directory" at top left and navigate to "data" directory under the installed game. From "Show files" dropdown list chose "Collections". Select the collection with swimwear textures (sb06_00.pp). From Type dropdown list select "Sexy Beach Zero" (it is not autodetected at moment).

At lower left list are all available textures from that collection. Select the one you like and click "Apply".
The selected material is now updated with chosen texture. As a next step, apply the same texture to panties and inner sides of swimwear.
Select "mn_mizugi_01_00" from material list. From dropdown list below select the new material created for bra (materialDNS_2) and click "Apply". repeat the same procedure from the inside of swimwear (mn_mizugi_00_01 and mn_mizugi_01_01).

And thats all. You have just imported Sexy Beach Zero girl with swimwear.

For posing there is skeleton mode (the small button with figure and blue bones in toolbar).
Before proceeding further it is good idea to familiarize yourself with document tree editor a bit - for example hiding bones without skin and extra bones you may not want to edit.
Importing scene is similar to importing figure - just make sure, that you import it as standalone object.

And last thing - save often. Khayyam is still alpha, so it has a bad habit to crash frequently.

Sexy Beach Zero

2010-12-13T10:59:00.000+02:00

SBZ is the latest hentai game from Illusion (look at ontopic Hongfire forum if you want to know more and do not mind erotic content). Like other Sexy Beach games, it's gameplay is quite unfun - woo girls, talk, date, and massage them, change swimwear and have sex - but it has upgraded rendering engine (although not very good) and, most importantly, semi-realistic (but still pretty) models. So I have spent the last days in trying to get Khayyam to read, render and pose those as well as possible.

To make character customization possible, models are composed of three separate parts - body, head and hair. Also - because the game allows you to "tan" girls - neither body nor head texture is embedded in mesh, but instead has to be loaded separately. Same with swimwear textures. Body also has extra "envelope" layer, that is used to guide hand and oil during oiling/massage scenes.

The skeleton has become even more complex, compared to previous models. One reason for this seems to be, that ingame body customization is now done with adjusting hidden bones.

Full skeleton of a SBZ model

The item and clothing collection is very uninteresting, like one can expect from Sexy Beach series. Maps are of better quality than in previous games, but there are only few of them.

Ai in jungle (rendered with POV-Ray)

And a render for you. It has too much focal blur, but I am too lazy at moment to make better one ;) The girl is Ai, who first appeared in Real Girlfriend, background is daytime jungle map from SBZ. Lighting consists of one area light (daylight) plus 2 greenish spotlights to illuminate shadows.

How to merge animations?

2010-11-18T16:21:00.000+02:00

There are two basic problems with copying animations from one figure to another:

The skeletons do not match. First, the body proportions are off, especially if converting between male/female or realistic/stylized characters. And secondly, the non-obvious bones are often arranged completely differently. By obvious bones I mean the ones like armbones, shins and so on, that connect two visible joints. Non-obvious bones are hidden and their joints are not immediately visible - like backbone or shoulders. Thus the exact number and placement of such bones may vary, depending on how realistic and fluid motion is needed and how it is achieved.
The bone orientations do not match. Even for bones that are perfectly aligned, like arms, the local coordinate systems can be very different and thus the transformations from one skeleton cannot be immediately carried over to another.

How to deal with it?

In Khayyam I am currently doing the following procedure:

Create one-to-one links between the well-defined bones of each skeleton - i.e. legs, shins, arms, forearms and heads. These function as anchors for matching body movements via IK solver.
Pick rootmost joints of matched bones, i.e. hips and shoulders as anchor point pairs.
Find the bone chain leading to last common ancestor of such pairs (starting from the point where previous chain ended). I.e. we get chains like these:
3.1. Center_of_Mass -> Skeleton_Root -> Pelvis
3.2. Lower_Backbone -> Upper_Backbone -> Chest
Adjust chains, starting from rootmost, as closely as possible to anchor points using IK solver.
Point all well-defined bones to the same direction as the originals, using IK solver

As you can see, it basically works, although some constraints on joint movement would be nice.

A demo video showing how dancing moves for DAZ skeleton can be imported to Esk Anderson figure

About C++

2010-11-07T21:50:00.000+02:00

I have had love/hate relationship with C++ from the time I started using it extensively about nine years ago. Before that everything was C - for example Sodipodi was 99.9% written in C (the only exception was the interface to KDE file dialogs). Those were good old times...

The learning of C++ was mostly one big frustration. Few beautiful and useful features - buried in clumsy, unintuitive and ugly mess. So after trying out and throwing away one feature after another, I mostly joined the C with classes crowd. This is the style used in Khayyam/Miletos/Elea code. But even for this minor subset of features, the language is just implemented plain wrong. Some completely elementary, clean and logical things are missing - and on the other hand - extremely clumsy, opaque and hard to use features are present.

So following is my list of things I'll one day implement in my own C Successor(TM) language.

Keep classes and struct separate. Structs should be POD, classes should ALWYAS have pointer to RTI. So no virtual methods for struct - and who in his right mind will miss these?
Keep memory layout standardized. Seriously. Probably all C++ variants implement things in one way - but the specification refuses to fix things once and for all.
- Classes are struct(ure)s. Like in Java. Standardized containers having function pointers for virtual methods, RTI information, link to parent class and so on.
- All object instances have hidden data field in first position, that is - you guess it - pointer to class struct(ure).
- All nonstatic methods should have pointer to class instance as hidden first parameter. So you can call class method from C. It is implemented this way anyways - but why force people to jump through loops to use it.
Keep meta-language separate from core. Implement two-pass compiling or something (in addition to preprocessor).
- Operator overloading should be specified in some meta-language. This would allow really useful things, like implementing separate dot and cross operators for vectors and so on. It should be transparently translated into proper C code during metalanguage parsing pass and then compiled by normal C/C++ compiler.
- Templates should be specified in proper metalanguage instead of "yet another hack on top of C syntax" and translated into normal C code during compilation.

And for extra sugar - allow overloading the virtual method call operation. So I can actually subclass object systems from other languages without writing countless ugly wrapper classes.

Obligatory screenshot - Ichiro having break in a forest (needs better lighting actually)

Chibibel

2010-10-26T14:12:00.001+03:00

Chibibel is a character by DAZ3D.
Poser cr2 (character rigging) files are quite heterogenous. So until now Chibibel has been the main reference implementation for cr2 importer.

Things implemented so far:

Parsing actor tree with channels. Actors (or props) are just a fancy name for bones (or frames) - i.e. positioned and transformed controllers for skin data. Channels are elementary property controllers - like individual rotation angles, morphs and so on. The main problem is, that the whole cr2 file format is mostly just (text based) dump of internal Poser controller structure as opposed to properly designed file format, so it contains many duplicate entries and meaningless data.
Twist and joint bend zones (no welds yet). Poser is special because the bending of joints is controlled with different weights for each main rotation axis - and these are specified algorithmically by line segments, angles and spheres. I am somewhat sceptical whether this would allow more natural movements - the weight system with extra bones and constraints should IMHO be easier and more powerful. But maybe it would be too difficult to set up for 3D modeling novices...
Welding obj meshes. Obj files cut meshes to groups, that cannot have interconnections. So cr2 file specifies, which groups should have their identically positioned vertices merged.
Loading textures from image files. Poser has quite complex material system, but currently Khayyam only looks it for diffuse texture entry and loads it as plain texture. Hopefully more is coming.
Conforming objects can be dropped to the same figure object as body. They behave surprisingly well, moving and bending with skeleton. But morphs cannot currently be linked, so if clothing has conforming morphs, they have to be adjusted manually.
Morphs work, but their values are not saved in XML data.
Props can be loaded but cannot be directly associated with bones. Props is (another) Poser fancy name for immutable objects (like tools, buildings etc).

Kuroyume Unoffcial CR2 File Specification has been invaluable resource for digging through the cryptic character data of Poser files.

Obligatory screenshot - Chibibel selling pottery in market (rendered with POV-Ray)

First steps with Poser(TM) figures

2010-10-16T19:40:00.000+03:00

Khayyam can now load (no import dialog yet) some basic Poser figures. They are not even close to renderable status yet, but things are becoming more interesting now:
- Basic morphing works
- Skeleton transforms poses as twist/joint/joint angles to body
- Blending angles are implemented
- Spherical falloff zones work (somewhat)
- Color values are parsed from materials

The next things I am working on currently:
- Loading conforming meshes (like hair and clothes)
- Implementing bulges
- Welding vertices

Obligatory screenshot - chibibel from DAZ3D

Khayyam architecture

2010-10-08T22:57:00.000+03:00

Khayyam is a collection of handful libraries plus shell application written in Gtk+ toolkit. Most components come from Sourceforge Floyd project, but core components are borrowed from Sodipodi. The most basic building blocks are

1. libarikkei (Sodipodi)
This is a collection of utility libraries for file handling, unicode parsing, text file tokenizing and similar things. It has both C and C++ versions of some most basic functions and is implemented as small, self-contained library that can be directly included into project.

2. elea (Floyd)
This is (yet another) 3D geometry library written in C++. It is meant to be small, so only the subset of functions used in Khayyam (and some other) are implemented. Again, it is self-contained and can be directly included into project.

3. libnr (Sodipodi)
This is small, self-contained, anti-aliased 2D rendering library.

4. libnrtype (Sodipodi)
Compact text rendering library on top of libnr

5. sehle (Floyd)
3D engine for OpenGL 2, using libelea for algebra. It is meant to be mostly bare-bones layer, implementing only the most basic stuff, like vertex buffers, textures, display list and so on. It should be quite flexible regards to rendering pipeline.

6. thera (Floyd)
Small and compact DOM-like library for XML parsing. It implements basic parser and writer on top of libxml, node tree, basic mutation callbacks and transaction system for rollback (undo and redo).

7. miletos (Floyd)
Fat scene graph library on top of thera, sehle and elea. Implements all more complex things like various file format parsers, skeletal animations and so on. It borrows the basic design concept from Sodipodi (although is implemented in C++ instead of C) - it is written as typed object tree, parallel to the purely untyped tree of thera. Most editing can be done either directly for temporary editing, or by customizing thera nodes or attributes for permanend modifications.

8. khayyam (Floyd)
This is the application itself.

This is only the most basic overview. Next time I hope to write some more details.

Obligatory screenshot (Des Blood 4 models, Digital Girl background, rendered with POV-Ray)

What is Khayyam?

2010-10-04T16:51:00.000+03:00

Khayyam is a frontend tool to my experimental set of 3D (and related) libraries.

A scene composed in Khayyam and rendered in POV-Ray

In current incarnation it cannot do much. Still you can import some model formats, place and pose these, and render resulting scene in POV-Ray. Plus it is free software. And works under both Windows and Linux.

A small overview of Khayyam can be found here.

At moment I am working on Poser model format support. This will be the first step for Khayyam to become a serious rendering tool.