crystalspace3d.org/planet

Crystal Space and Crystal Entity Layer 2.0 beta 2 have been released.

Check out the Download page for downloads and see what's new.

---

Crystal Space and Crystal Entity Layer 2.0 beta 3 have been released.

Check out the Download page for downloads and see what's new.

---

Dear CS, CEL and Ares developers, users, supporters and all,

In the fast pace world of 3D, hardware and gaming. It is difficult to keep up and progress without the assistance and generosity of others.

CS, CEL and Ares are three core projects that now and in the future, bring you the ability to create games and other applications with a degree of ease and flexibility. Doing this though creates it's challenges. As Open Source projects, we survive on peoples generous donation of time and their passion which is so great they purchase much of the hardware to progress the projects from their own pockets.

We are reaching out to the community and wider to assist us if you can and reduce the burden from individuals and progress as we wish to. In the future we wish to:

 - Better support Apple Mac OS X

 - Add Android support

 - Add Apple iOS support

 - Add GLSL and GLES

We would also like to be able to purchase up to date versions of software for example Visual Studio for long standing developers. Other uses of any financial donations would be decided by concensus amongst the development team as they are at present.

As projects we are always looking for new people to help in all areas of the projects.

If you are able to offer your time to any of the projects please contact us via the discussion or development mailing lists.

To subscribe and mail to the list, please see:

http://www.crystalspace3d.org/docs/online/manual/Mailing-Lists.html

As projects we are in desperate need of hardware and software to bring support and features up to date then progress, and as a team of individuals we can only do this via donations in the future.

If you are able to make a donation of money or hardware. Please contact the founder of the CS, CEL and Ares projects:

Jorrit Tyberghein - Email: jorrit.tyberghein@gmail.com

Regards

Phil Wyett

Crystal Space and Crystal Entity Layer release manager.

---

They say you wait ages for a bus, and then two turn up almost at the same time.

Hot on the heels of last weeks 2.0 beta 1 releases. The Crystal Space and CEL Development Teams are pleased to announce the release of Crystal Space and CEL 1.4.1.

This is a support release of the stable 1.4 series. It includes updates, fixes and other changes.

This is a supported release. However, we must note that this release will be last in the 1.4 series and efforts will now move to the upcoming 2.0 release and other future developments. More on these in the coming weeks and months.

Check out the Download page for the files and further information.

---

As scheduled and on time.

Crystal Space and Crystal Entity Layer 2.0 beta 1 have been released.

Check out the Download page for downloads and see what's new.

---

'Guano covered demons from hell!' Exclaimed the preacher, 'I'll be a gypsy whore wobbling O-legged through the doors of this church after a long night out in town If I'd ever let you enter this holy place dressed like that!' I wasn't trying to make a fashion statement, this banana coloured thong was the only piece of clothing still in my possession after Thick Tony raided my place...I figured I'd try my luck anyways 'Sanctuary?' I requested humbly. This just seemed to enrage the man of the cloth even more.... Why was Tony at my place? I haven't pissed him off for at least 3 years, not since I won against him in a match of poker and he carved the now clearly visible 'IOY' in my chest. What changed? Taylor was at my place last month...sweet Taylor involved with Tony's affairs, the thought sends a chill up my spine. Maybe if I had been nicer to her, I could have kept her out of trouble. I dodge a collection plate, the preacher hasn't given hope on kicking me out of his church. I need a lead or at least some clothes, it's already dark outside maybe I'll take my chances on the street. I need a contact, someone that wouldn't run away horrified seeing me like this, Crazy John comes to mind, John has seen it all, the outskirts of Vegas, donkey shows in Mexico, midget wrestling in Texas, midgets wrestling donkeys and every fan art forum on the internet. If there was a person on this globe that could see me like this and consider it the most normal event in his life, it would be John, but would he have reinstalled his passenger seat already? I could use a ride. Empty drive way, shit he's not home! My eye catches a shimmer of the porch light in a piece of glass near the fence, I walk towards it and pick it up, a remnant of a glass jar covered in blood. What happened here? There's something in the weeds as well, a face plate of a Cisco router... Olathe, a crime hub? I chuckle and toss the face plate and bloody piece of glass on the ground. Maybe he's at the warehouse with Brant? I start jogging in its general direction. Have you ever seen a grown man jog in a yellow thong, if you haven't, don't try to mentally picture it, it's not a pretty sight! But I digress, why was Tony after me? Or what and why was it at my place? It doesn't even matter anymore, I'm tired and cold, I just want someone to hold and fall asleep with. Preferably not in this outfit.

The Ares Project is looking for C++ developers and 3D/2D/sound artists! Ares is a new ambitious project managed by Jorrit Tyberghein. The project is divided in three parts:

• A Game Editor called AresEd. This will be the tool that the game designer(s) can use to make games. It is going to be a general tool so it is useful for more then just Ares. This tool is currently already functioning but a lot of work is still needed to make it really usable.
• A Game Player that will be able to play games made with AresEd. This tool will be heavily based on CEL. Most of the game logic and coding has already been done on this part of the project.
• An actual game based on the above tools. Check out the Ares Project page to learn more about this game!

---

The Development team at ‘Tempest in the Aether’ would like to announce a free, completely open source, Steam Punk styled MMO using the PlaneShift implementation of the Crystal Space 3D engine. The game is currently in an early stage of development producing a technical demonstration of the game.

This will include:

• A fully functional game server and cross platform support for the game client.
• An initial map.
• Several Steam Punk styled Automatons.
• A fully functional and active quest system.
• A custom recorded sound track and environmental audio and in depth settings.

To view and current status and follow the progress of the game visit the Tempest in the Aether web site at www.tempestintheaether.org and join the team on their forums.

If you would like to chat with the team, see what they are up to, ask about the game or perhaps about offering your support to aid developing Tempest in the Aether then please join them on IRC.

• Server: irc.freenode.net
• Channel: #Tempest-in-the-aether
• WebIRC Link:#Tempest-in-the-aether

If you are interested in viewing some of the concept and 2D/3D art which has been created for Tempest in the Aether then either please visit the online galleries at www.tempestintheaether.org/gallery

Or visit a collaborators site, OpenGameArt.org. Which brings like-minded coders and artists together to create Open Source video games, by providing a database of freely-licensed art resources. Searching for ‘Tempest’ will bring you results for items made for us but licensed openly http://opengameart.org/search/art?keys=tempest

---

I ran out of roads to walk down and sailed the seven seas, more than men but less than a man, my ashes blowing in the wind and my words turning to whispers on the lips of the ones that once knew me.

Masks is what we wear, the truth is behind it, not out there. Made from cardboard, plastic or papier-mache, we think it hides all our cares away. Sometimes we switch masks, but we never take it off, afraid forever, to love.

Because this project also served as my MSc Individual Project at Imperial College London I have written a report and a presentation for it as well.

You can also see what this project does in less than 3 minutes from the following video:

Although the final deadline for this project has passed there are still a couple of things left to be done. I have split them into two main categories: implementation, improving and extending on the existing code / ideas and algorithm, introducing new ideas that should give better results.

• Implementation
  

The existing render manager can be improved by extending it to support:

1. Multiple lights – at the moment only one light is supported. Multiple lights can be added by using a 3D texture, because every light generates a maximum of up to 10 textures.
2. Multiple mesh types – for now only genmesh is supported. Although this is the most generic type of mesh used in Crystal Space, support for materials from other types of meshes has to be added as well.
3. Rendering smoke and clouds – this will involve adding a volumetric rendering technique and apply the algorithm from the current render manager without any further modifications.

• Algorithm

A couple of ideas can be added to produce better renderings or make the application run faster.

1. Different split ratio for each ray – at the moment the split ratio is computed globally and this causes problems when objects with different densities are present in the scene. One possible way of having a unique split function for each ray is by creating a split texture, storing the split ratios for each individual ray onto a corresponding pixel.
2. Recomputing the split ratio in real-time – this is the current implementation bottleneck, because it is done on the CPU. If the split ratio will be computed for each ray, then no global information will be needed and the computation can be done faster on the GPU by adding a new image processing render pass.
3. Compute the optimal number of layers – the number of layers is currently chosen by the user. However, a test scene can be created so that the maximum number of layers that keeps the application real-time will be automatically chosen.
   

As a final step for this project I tested the performance of the three algorithms I implemented throughout the summer: Opacity Shadow Maps (OSM), Deep Opacity Maps (DOM) and Bounding Opacity Maps (BOM).

I measured the performance in frames-per-second (FPS) using the average FPS provided by Fraps benchmarking tool for a period of 60 seconds. The GPU card (Nvidia GT 335M) had the most important contribution in the measures taken, because all three algorithms are GPU bound (they involve rendering to texture multiple times and no significantly computational task is done on the CPU).

The performance is shown in Figure 1

Figure 1 Plot generated using gnuplot. The variance between the number of layers and the FPS for the three algorithms implemented for this project. Even thought Bounding Opacity Maps have the worst performance they produce realistic renderings even when using the minimum number of layers tested because they follow the real-world light’s distribution (BOM).

• Blinn-Phong shading model

The methods presented so far give only information about shadows cast by translucent objects on themselves.  In a Blinn-Phong shading model this would correspond to the diffuse lighting, but the specular and the ambient lighting have to be added as well. These two terms were used as described in the Blinn-Phong model (Figure 1), although for the specular component more advanced techniques such as Kajiya and Kay or Marschner could be used when rendering hair.

Figure 1 Picture from Crystal Space. Scene rendered without any specular or ambient lighting (a) and scene rendered using these two terms as described in the Blinn-Phong model (b).

• Shadow mapping

Opaque objects were introduced in the scene by using the depth map that computes the initial splitting positions. This map is actually a regular shadow map, so adding opaque objects to the scene was just a matter of applying a common shadow mapping algorithm without any additional computational costs (Figure 2).

Figure 2 Picture from Crystal Space. Opaque objects don’t cast shadows (a) and cast shadows using shadow mapping (b).

As I mentioned in the previous post a hybrid split between the linear and the logarithmic split can be a good idea because when the linear splitting scheme falls short the logarithmic one can be used and the other way around.

Because when multiple layers contain the same information artifacts may occur, the criteria for choosing the ratio between linear and logarithmic splitting is so that it produces consecutive layers as different from each other as possible. Or put in another way each new layer should bring new information. In terms of computer vision this can be translated to having the mutual information between these images as small as possible.

Two techniques of measuring mutual information were tested: sum of absolute differences and cross-correlation coefficient.

The sum of absolute differences is pretty straight forward to compute and it involves adding the absolute value of the difference between each two corresponding pixels from the two images.

The cross-correlation coefficient represents the ratio between the covariance of two images and the product of their standard deviation, and can be computed using the following formula:

where Ī(•) is the mean of image I. Another useful property about correlation is that it has values on a scale ranging from [-1, 1] and it gives a linear indication of the similarity between images.

As expected from the findings in the previous post the mutual information is smaller when choosing a more linear split for sparse objects and a more logarithmic one for denser objects (Figure 1).

Figure 1 Plot generated using gnuplot. Linear splitting corresponds to a split ratio of 0 while logarithmic splitting maps to the value of 1.

Because, as we can see from Figure 1, the cross-correlation coefficient (shown in green) covers a wider range of values, giving better estimate for each density value, it was chosen as the default method of computing the mutual information. The cross-correlation probably performs better due to the influence of standard deviation, which is completely neglected for the sum of absolute differences (shown in red).

Well,  GSoC came to an end and I thought I’d post an update.

As a quick refresher, my project involved adding video decode support to the open source engine CrystalSpace. Everything turned out ok, so I’m gonna talk a bit about it.

I added video decode support through Theora, and open source video compression format. The basic idea behind my implementation was to have the main thread to render the scene, and another thread to decode video frames and convert data from the  YCbCr colorspace to RGB. Then, in the main thread, data would be written to one of the buffers, and the buffers would be swapped. I used double buffering.

If I had to give a few tips on video decoding, here’s what I’d say:

1. Threads

If you can, avoid them. Threads introduce concurrency and code that ran perfectly before, will probably run slower and you won’t know why. If you can get just the right amount of processing transferred over to another thread, you’ll get a speed boost, but you’ll have to experiment quite a bit. In my project, I used threads, because you can’t just use up the main thread (which renders and updates the scene) to do your dirty work. It worked well in the end, but it was a bit of a pain in the ass. Here’s a nice article on threads.

2. Conversion

Depending on the colorspace supported by the surface you render the video frames to, you will have to do conversion. I did it on the CPU using Look-up Tables, and it worked well, but just for the 4:2:0 pixel format. 4:2:2 and 4:4:4 were too slow to be useable. My advice, if you’re doing conversion on the CPU, is to use MMX. I ran some tests on MMX during my project, and it turned out about 2 times faster. Implementing conversion in MMX using LUTs isn’t really a hard thing, but you’ll have to watch out for different compilers. asm tags are usually different for each one. Unfortunately, I din’t have time to move conversion to MMX. In any case, here’s a paper about optimizing YUV->RGB conversion. Alternatively, you can do conversion on the GPU, using a shader. Again, I didn’t have time to implement this, but here’s a reference.

3. OpenGL

The main problem I ran into during this project is that openGL doesn’t support multi threading (as far as I know, oGL 3 and up do support it). This is a big problem. You can’t access an openGL context from outside the thread it was created in. This is annoying because, if you’re processing an openGL resource on another thread, you need to place a callback in the main thread to apply the changes, which slows you down. Admittedly, the slow down isn’t that big, but you’ll see a huge difference between single threaded implementations and multi threaded ones. For example, w/o multi threading, converting th 4:4:4 pixel format (the one used for 720p vids) was pretty fast. As soon as I moved conversion to another thread, due to the synchronization induced by this, it was now too slow to be practical.

 

In any case, the project turned out OK, and I’m happy with it. Learned a lot of things this summer. It was a really nice experience.

This also means I can get back to game dev Gonna post a prototype as soon as I have one

Peace

Filed under: awkward, CrystalSpace

• Linear splitting

The most frequently used splitting scheme for choosing the opacity maps’ position is the linear one. It has been used as the primary splitting scheme in both opacity shadow maps (OSM) and deep opacity maps (DOM).

However, if we were to look at the light’s distribution on real-world translucent objects such as clouds, trees or hair we can observe that for dense objects the lighting caused by self-shadowing changes only at the very beginning of the object (Figure 1).

Figure 1 Real-world photographs of clouds (a) and bushes (b). It can be observed that for these objects the lighting only changes at the very beginning of the object.

In such cases a linear distribution would produce layers that contain almost the same information from a certain layer onwards (Figure 2). A distribution that would have more layers near the beginning of the object and fewer at the end would probably give better results.

Figure 2 Layers obtained using linear splitting on a scene with a dense model. The last four layers contain almost the same information.

• Logarithmic splitting

The logarithmic distribution has a slower increase rate and therefore produces a splitting that has a higher density of layers at the beginning of the object (Figure 3).

Figure 3 Comparison between linear and logarithmic distributions. Linear increase, blue, versus logarithmic increase, green (a), linear split (b) and logarithmic split (c).

Obtaining layers that have different shadow information prevents artifacts like the ones shown in Figure 4.

Figure 4 Difference in rendering when using linear splitting (a) and logarithmic splitting (b). Linear splitting (a) produces incorrect self-shadows because most of the layers contain the same information (Figure 2).

•  Hybrid split

Although logarithmic splitting produces good results on dense objects, it doesn’t preform well on sparse objects because the lighting caused by self-shadowing changes throughout the entire length of the object (Figure 5).

Figure 5 Real-world photographs of clouds (a) and trees (b). It can be observed that for sparse objects the lighting changes throughout the entire length of the object.

The rendering artifacts that occur when logarithmic splitting is performed on sparse objects can be seen in Figure 6.

Figure 6 Difference in rendering when using logarithmic splitting (a) and linear splitting (b). Logarithmic splitting (a) produces artifacts: the willow is incorrectly lit near the top, because the layers don’t uniformly cover the whole length of the sparse object.

However, because the linear splitting scheme can be used when the logarithmic one fails and vice versa, using a hybrid split between the two of them based on the given scene should produce artifacts free renderings. More on this hybrid split in the next post.

As mentioned in the previous post, the main problem was that Cg allows to specify vertex/fragment shaders independently whilst GLSL does not. In fact as I explained last time, GLSL shaders require a linking process that binds the vertex and the fragment shader together. The linking process makes a GL object called a "program" which represent an entire pipeline itself. Shader parameters and other stuff are acting on this object. The shader plugin system of Crystal Space wasn't much designed this way, however layers on top of the plugin system are considering a shader as a pair of vertex and fragment shader, which simplified the work.

Basically, Crystal Space wraps vertex and fragment shaders (csShaderProgram, which implements iShaderProgram) into a single csXMLShaderTech class that is used for rendering. The shaders are specified in the corresponding XML shader file. The basic idea was "iShaderProgram should represent an entire pipeline (so a set of shaders) instead of a single shader". To ensure backward compatibility, this was achieved by adding a simple wrapper class, csXMLShaderWrapper, that holds a vertex and a fragment shader from the old Cg or ASM plugins.

The new GLSL plugin doesn't need to use this wrapper since the shader object provided already contains an entire pipeline, ready to use. A new XML syntax has been setup for shaders that don't need wrapping. You were currently specifing shaders like this:


<pass>
<vp plugin="glcg">
<cgvp>
<program>
<![CDATA[ /* code... */ ]]>
</program>
</cgvp>
</vp>
<fp plugin="glcg">
<cgfp>
<program>
<![CDATA[ /* code... */ ]]>
</program>
</cgfp>
</fp>
</pass>


As you can see, plugins are specified independently; a GLSL plugin could hardly fit this design. The following syntax has been defined for the new plugin:


<pass>
<shader plugin="glsl">
<vp>
<program>
<![CDATA[ /* code ... */ ]]>
</program>
</vp>
<fp>
<program>
<![CDATA[ /* code ... */ ]]>
</program>
</fp>
</shader>
</pass>


The "unification" is made more explicit and the code is lighter.

Because Deep Opacity Maps (DOM) give information only about the starting position for the splitting points, two major issues appear:

1. The position of the splitting points can’t be precisely determined for any type / shape of object because the end splitting position is not specified.
2. The layers only follow the light’s distribution at the beginning of the object, where the start points are known via the depth map (Figure 1).

Figure 1 A translucent full sphere as seen in real-life (a), the distribution of layers when using DOM (b) and the way the light is distributed in real-life (c).

Furthermore, the example from Figure 1 is not a particular case, the light distribution following the shape of the object for other translucent real world objects, such as blonde hair or trees, as can be seen in Figure 2 and Figure 3.

Figure 2 Real-life lighting of blonde hair (a) and the corresponding layers and light distribution (b). It can be observed that the layers and the light distribution follow the shape of the object.

Figure 3 Real-life lighting of a tree (a) and the corresponding layers and light distribution (b). It can be observed that the layers and the light distribution follow the shape of the object.

By computing an extra depth map, in which depth information about the furthest away points is given, instead of the closest ones, the limitation of DOM regarding the lack of information for the end splitting points is solved, and more important the layers follow the light’s distribution in real-life.

This is achieved by Bounding Opacity Maps (BOM) where the layering follows the light distribution in real-life by interpolating the values from the two depth maps when choosing the splitting points.

The difference in splitting between DOM and BOM in Crystal Space can be seen in Figure 4 and the difference in rendering in Figure 5.

Figure 4 Difference in splitting between DOM (a) and BOM (b) when using 16 layers – first layer corresponds to light green and the last layer to black. It can be seen that because the end splitting points are not specified in DOM the layers don’t cover the whole length of the object (the final color is not black as in (b)).

Figure 5 Difference in rendering between DOM (a) and BOM (b) when using 16 layers. Because DOM don’t specify the end splitting points some grass strands (from the red circle), corresponding to the last layer, are given false shadow information.

Deep Opacity Maps (DOM) represent a nice way of removing artifacts caused by the linear splitting in Opacity Shadow Maps (OSM).

The novelty of DOM is that they align the opacity maps (layers) with the hair geometry by first computing a depth map and use this information as an offset to the linear splitting that happens at a later rendering pass. In the following picture taken from [DOM] you can see exactly the difference between splitting in OSM (a) and DOM (b).

The advantage of using DOM is that visual artifacts do not occur even when using just a few layers, because by being aligned with the geometry the splitting follows the light distribution. Next is a comparison between the rendering obtained with OSM with 60 layers (a) and DOM with 16 layers (b) in Crystal Space:

However, one major disadvantage of DOM is that even though they explicitly specify a starting splitting position for each point (via the depth map), no information about the stopping splitting position is given whatsoever. This can create a lot of difficulties when trying to make the implementation work with different objects of different sizes and shapes. Using either a constant or the length of the object measured at a particular point in order to obtain the distance between two consecutive splits are too restrictive and thus fail.

This is why for the remaining time of the project I plan to extend DOM to compute and use information from a depth map containing the depth of the farthest points (the stopping splitting positions) as well. I also want to experiment with different splitting schemes, apart from the linear one, and add support for opaque objects, possibly by using the information provided by the depth map.

Here are some of the first results of my implementation of SSAO plus one bounce of indirect light in the Crystal Space engine. In the photo gallery you can see three pictures of the famous dragon model from the Stanford repository in the Sponza Atrium scene. The first one is rendered with ambient occlusion and [...]

Opacity shadow maps can suffer from sever artifacts if not “enough” maps are generated. The artifacts are caused by the fact that new points, without shadow information, are introduced by each opacity map. Below you can see the grass from CS rendered using only 15 opacity maps (the diagonal lines perpendicular to the light’s direction are the artifacts, in case they weren’t obvious enough ):

The limit is 15 because, at the moment, the textures are passed as an array of sampler2D and only 16 (15 opacity + 1 material) textures can be used in one shader on my video card, NVIDIA GeForce 9500M GS. However, 4 times more maps can be generated if every channel of every texture is used, yielding 60 maps (but only 14 textures):

As can be seen from the above picture the artifacts are now slightly less visible (more but smaller), so increasing the number of maps is one way of trying to remove these artifacts. Another (smarter) way is by aligning the opacity maps with the geometry, using information from a depth map, as described in deep opacity maps (DOM). This is what I plan to implement for the second part of GSoC. Here is how DOM should improve the rendering:

After roughly a month of coding I managed to implement the render manager (RM) for opacity shadow maps (OSM).

The basic idea with OSM is slicing through the translucent object(s), with planes perpendicular to the light’s direction, and rendering to texture multiple times. These maps store the translucency amount (obtained using additive alpha blending) at particular distances and are used to approximate the translucency of every point from the object (the opacity function from the following picture).

Picture taken from OSM.

At the moment the OSM RM only supports a linear splitting scheme (interpolation), though it supports both multiple objects and lights. Next I will work on some more advanced splitting schemes, that should get rid of the visual artefact from linear splitting and also do some optimizations regarding the rendering targets and the collision test for each split.

Below you can find a comparison between OSM with 4 and 8 slices and the parallel split shadow maps implementation (PSSM) from CS:

• PSSM

• OSM with 4 splits

• OSM with 8 splits

Welcome to my GSoC 2011 blog! Here you'll be able to follow the progression of my project for Crystal Space.

This is my first time participating to the Google Summer of Code, and I'm glad I've been accepted into the project I was most interested in. My project will consist of, basically, add support for OpenGL GLSL shaders into Crystal Space, which currently provide support for OpenGL ARB and nVidia Cg shaders. Ideally I'd also like to add support for the famous geometry and tessellation shaders, which would allow Crystal Space to implement new generation and cool rendering techniques based on them. The project will be implemented as a Crystal Space plugin.

The main design difference between Cg (and ARB) and GLSL shaders is that Cg allows you to bind the vertex and fragment shaders independently while GLSL requires them to be linked (and thus non-separable) into a "program" before being used. Fortunately, Crystal Space's architecture doesn't use much of the "separable" functionnality provided by Cg, facilitating therefore the setup of a "unified" design, much like GLSL's. This will involve a new syntax in the XML shader files used by Crystal Space in order to make explicit the use of the "unified" model.

I hope that by the end of the summer I could provide a nice tessellation demo, but for now I have to focus on the core of the new GLSL plugin and its integration into the engine.

Have a nice summer! :)

I have just created a new blog for my GSoC 2011 project, regarding “Real-Time Volumetric Shadows for Dynamic Objects”. At the end of this project I should be able to obtain a more realistic hair rendering as well, by using self-shadowing.

You can check it out at: http://volumetricshadows.wordpress.com/

Before developing the new render manager (RM) for opacity shadow maps (OSM) I built a scene that can show the difference between various RM in CS. This scene contains some translucent objects, such as grass and a cloud made out of spheres. I built the scene using Blender 2.49 and exported it via blender2crystal.

Here is the scene rendered by 4 different RM:

• unshadowed – this is the default RM in CS, and it renders the scene without any shadows

• deferred – the deferred shading from CS, which was a previous GSoC project, see more at: http://www.joeforte.net/

• shadow_pssm – a parallel split shadow map implementation (PSSM), which is the only shadow RM present in CS

• osm – a prototype of what I am going to implement, which is just a striped version of the unshadowed RM at the moment

As a side note PSSM are basically the same thing as Cascaded Shadow Maps (CSM), which I also wanted to implement for this project because they use multiple shadow maps and rendering positions, similar from this point of view to OSM. However, because they are already implemented I went directly to writing the OSM RM.

So this is my second year at both Google Summer of Code (GSoC) and Crystal Space (CS) after the last year’s project, which you can find at: http://hairrendering.wordpress.com/.

This year I plan to implement “Real-Time Volumetric Shadows for Dynamic Objects”, by adding a new render manager in CS.

This idea came to me while trying to figure out why my hair rendering didn’t look as good as advertised by other demos, such as NVIDIA Nalu. The reason is that my hair plugin lacked self-shadowing and so I studied how this can be implemented by doing an Individual Study Option at my university, regarding “Rendering real-time self-shadowed dynamic hair”. You can find my presentation here.

For this project I plan to implement Opacity Shadow Maps (OSM) for starters and then implement some more advanced techniques, such as Fourier Opacity Mapping (FOM) and/or improve the OSM by using a different sorting algorithm.

If you would like to view the implementation, as it progress, you can check out via SVN the CS selfshadow branch (no account needed). Also, if you experience problems compiling CS, you can read this post here (it’s a little bit old, but it should do the trick).

In early April I made a proposal to participate in Google Summer of Code program at Crystal Space and it was accepted!

GSoC is a program where several students all over the world (around 1000 every year since 2005) are chosen to work on different open source software projects over a three-month period.

Crystal Space is (quoting from its website):

A mature, full-featured software development kit (SDK) providing real-time 3D graphics for applications such as games and virtual reality.

For the next few months I’ll be working in extending the deferred shading manager with a technique called screen space directional occlusion. In the next days I’ll be posting more details about the project.

Well, I’ve been following GSoC for a while now and I finally decided to join. I found a nice graphics engine called CrystalSpace which needed video decode support. So that’s what I’m gonna do.

Wish me luck!

Filed under: awkward, CrystalSpace

The projects for the Google Summer of Code 2011 at Crystal Space have been chosen.
We are happy to have got once again six slots.

Here is the list of accepted projects:

• Antony Martin: support of GLSL shaders
• Santiago Sánchez : approximating dynamic global illumination
• Alexandru-Teodor Voicu: real-time self-shadowing for dynamic transparent objects
• Matthieu Kraus: adding OpenCL support to lighter2
• Liu Lu: improvements of the collision and physics systems
• Alin Baciu : Video decode support

Congratulations to our students, commiserations to all others who have unfortunately not been accepted, we encourage them to try again next year!

---

Crystal Space is a mature, full-featured software development kit (SDK) providing real-time 3D graphics for applications such as games and virtual reality. It is free (LGPL) and cross-platform (Windows, GNU/Linux, Mac OS X).

The project encompasses two main components:

	Crystal Space — A modular, configurable, and extensible rendering engine supporting OpenGL and advanced features such as shaders and lighting systems, physics, 3D sounds, animation blending, foliage, terrain, virtual file system, physical peripherals, and more.
	CEL — Entity system supporting higher-level functionality, such as runtime package environment (CELstart), generic event system, avatar and camera management, artificial intelligence (behavior trees, path finding, neural networks and genetic algorithms), vehicles, and more.

Related projects: YoFrankie!, PlaneShift, Blender (blender2crystal), Project Ares, Peragro Tempus.

---

Recent News

As scheduled and on time.

Crystal Space and Crystal Entity Layer 2.0 beta 1 have been released.

Check out the Download page for downloads and see what's new.

---

• Older news...

I'm a research assistant at the Electrical engineering department of the Institute of Information and Communication Technologies, Electronics and Applied Mathematics at Université catholique de Louvain, Belgium.

We are setting up an Immersive Virtual Environment to be used by psychologists for experimentation and therapy, and we have chosen Crystal Space as the game engine that will simulate and render our environments.

We will therefore keep working and using Crystal Space, and particularly its animated mesh. One of the main task that we plan to work on in the next months is the implementation of the hardware skinning pipeline that is still missing.

I also started this blog in order to give more transparency to the public on what is going on in Crystal Space. I'll try to present here regularly the new features that are added by the CS team.

This post will talk about the different ways to import assets into Crystal Space, and will present the recent improvements that have been made about that.

Guided tour of the import of assets into CS

CS had until now several different solutions to import the models and scene objects from the many different 3D design tools and file formats.

Blender has always been until now the editor with the best support for CS. The blender2crystal project is a huge piece of software, with many advanced functionalities such as import and export of CS files, CS previsualization window directly embedded into Blender, animation tree edition, etc. Unfortunately, the blender2crystal project is no more active and has been overtaken by the Python 2.6 and Blender 2.5x series, it is blocked to the Blender 2.49b with Python 2.5 version and may hibernate there forever.

Currently, the solution to export data from Blender 2.5x into CS is to use the B2.5CS exporter from Peragro Tempus. It does not yet have support for animeshes, but it is planned to become the official exporter for CS and should therefore be improved in the future.

3D Studio Max had also some rather good support with either the exporter script from the PlaneShift team or the exporter plugin added recently by Mike. And for other 3D design tools and model file formats, CS had several solutions with either dedicated importers and/or exporters for COLLADA, Maya, Cal3D, md2, BSP.

And there there was... the Assimp plugin

So this was the situation until recently, but a big part of this has now been obsoleted by a new addition made recently to CS, namely the new plugin for the Open Asset Import Library (A.K.A. Assimp).

As suggested by its name, Assimp is an open source library providing a generic interface to load 3D models and scenes from a huge list of different file formats. It can import the meshes, the material properties, the skeletal animations, the lights, cameras and complete scenes. The support for vertex and morph animations is planned but not yet implemented. The support for meshes and material properties is rather excellent for all the listed file formats, while the quality of the import of the animations may vary depending of the format.

The Assimp plugin that has been implemented in CS uses the new guidelines for the preprocess and tool plugins. This basically means that the plugin is integrated completely transparently into the CS loader system: you simply drop any asset file of one of the format supported, and it is loaded magically in CS, without any further need to manipulate or export/import previously the file.

An example has been added in CS with the Seymour COLLADA animated test model. It is composed of one data file and one texture file that have been packed in a ZIP file in 'CS/data/seymour.zip', and the following image is the result of the command:

• 'viewmesh -R=data/seymour.zip Seymour.dae'

Technically speaking, this plugin simply implements the iBinaryLoaderPlugin and iModelLoader interfaces of CS, as any other CS-specific loader plugin. Therefore, when the iLoader is used to load a file, the Assimp plugin will be selected if it supports the file format. It will then analyze the file, and import the objects as genmeshes, animeshes or whole scenes depending on the loader interface used and the options that have been set.

Another interesting feature of the loading system of CS is that the definition of an object can be split in several files. It is therefore possible to have your model in its base format and being kept updated by your artist team, while still being able to already use this model in your application and extending its definition with CS concepts such as physics or more advanced management of the animations. These concepts will simply be defined in a separate CS XML file and will add their data ontop of the one loaded by the Assimp plugin.

Morph targets

A problem that has been mentioned about the Assimp library is that it does not yet support the import of vertex and morph animations. To overcome this, some tools have been added to CS in order to load and merge an animesh with its morph targets defined in several different files. Again, this functionality has been made using the new guidelines for the preprocess and tool plugins, meaning that you can activate this process transparently through the iLoader interface. An example of that has been added, using the default model from the FaceGen software. Here is the result of the command:

• 'viewmesh data/jane/jane.cslib'

Lastly to be mentioned, there is the new exporter plugin for the PnP TerrainCreator editor, that has also been added recently by Mike. This last plugin should be presented more closely in an incoming post on the new 'csisland' demo.

Sorry, but that will be a rather long post. Hopefully I will post more regularly in the future...

Most of the work that was made until now was about procedural animation, at first with the physical simulation thanks to the Bullet physics library, then with skeletal animation with improvements to the new animesh. All this work will be available in the incoming 2.0 release of Crystal Space.

The Bullet's physical plugin

The Bullet plugin of CS was only partially implemented and suffered of several bugs and problems. The plugin has now be completely overhauled and almost all the features of the initial iDynamicSystem interface have been implemented. As a result, the Bullet plugin is now fully useable, and is clearly preferable compared to the ODE plugin, simply because it works much better and has much more features. The 'phystut' application demonstrates how to use most of these functionalities.

In addition to that, several new features have been added. Most noticeable are:

• Kinematic objects for objects acting on the physical simulation but controlled by the user. You can attach a mesh to it in order to have it updated automatically when the mesh is moved.
• Soft bodies to simulate deformable objects such as flags, clothes, ropes, etc. A new animation controller (CS::Animation::iSoftBodyAnimationControl) and some utilities (CS::Physics::Bullet::SoftBodyHelper) have been written in order to create easily a soft body from a genmesh and to animate the genmesh depending on the results of the simulation. The controller is also able to maintain correct anchoring of the soft bodies when they are attached to an animesh which has a deformable topology (see below).
• Terrain colliders integrated with the terrain2 mesh. They are able to load and unload automatically the terrain cell's colliders on demand.
• Debug plugin to display information on the colliders and the objects of a physical scene. This plugin works with both the ODE and the Bullet plugins.
• Physical hit beams and grab joints.

The main functionalities missing are the setup of the information of the collisions and the filtering of these collisions.

The animated mesh system

The animesh (namely the class CS::Mesh::iAnimatedMesh) which was introduced during the YoFrankie project has been improved a lot. Many already existing features have been improved and fixed, such as the sockets, the blending of the animations, the import with blender2crystal, the Finite State Machine animation node, the computation of the bitangents, the display of the animeshes in viewmesh, etc.
Both the skeletal and the morphing animations have also been optimized and run now decently (although all computations are still made only in software).

Many new features have also been implemented, most of them are visible in the 'avatartest' application:

• A new high detail test model has been made specifically for Crystal Space: Krystal. This model has been made thanks to the great help of a friend nicknamed Korbak. It is made in Blender and is based on the Gothic Woman model by Tiziana. At first, a Blender script was written in order to import motion captured animations into this model, but a much better solution has been implemented after that (see below).
• Definition of the "bodymesh" (class CS::Animation::iBodySkeleton), holding the geometric and physical description of the skeleton of an animesh. Bone chains can also be defined to represent sub-parts of the skeleton (to be used e.g. by Ragdoll or Inverse Kinematic nodes).
• New "Ragdoll" animation node. This node can manage automatically the physical model of the animesh, and put parts or whole of the skeleton in a dynamic or kinematic state. The dynamic state allows to have some parts of the skeleton animated by the physical simulation, e.g. to animate props or dying avatars. The kinematic state is useful to have the animesh interact with the physical scene, and to attach some soft bodies to it.
• New "Lookat" animation node. This node can control a bone of the skeleton in order to make it look at a given target. It is useful to bring life into an avatar and making it more responsive to what happens in the scene. The animation node handles automatically the transitions when the target gets in and out of visibility, so there's no need to manage the transitions at a higher level (but the exact behaviour is configurable).
• New "Speed" animation node. It takes as input a set of animations of the mesh moving at different speed (e.g. idle, walking, running), and blends them together to achieve any custom speed in between.
• New "Inverse Kinematics" animation nodes. Such nodes allow to control the position of an end effector placed on a sub-chain of the skeleton. It is useful to control the precise position of some bones of the skeleton such as the hands or the feet. There are two different implementations of this node, one is a quaternion version of the Cyclic Coordinate Descent algorithm, the other uses the physical simulation in order to achieve the effect.
• New "Retarget" animation node. This node can retarget an animation from one skeleton to another. It is useful for example to re-use animations or to input motion captured data into your animesh. The two skeletons must have a similar topology and limb proportions, otherwise the results won't look good. To overcome this, the behavior of the retargeting can be tweaked, but a more advanced solution would be needed in the future.
• New "Debug" animation node. It currently simply allows to display the state of the skeleton.
• All animations and nodes can be loaded from the CS's XML scene description file format. A facility has also been setup to manage easily the splitting of the definition of the objects in several different resource files.

This is not the end of the list of new functionalities:

• Decals can now be defined on animeshes, allowing an easy personalization of the meshes. The decals are updated automatically to match the deformations of the animesh.
• Clothes (i.e. physical soft bodies) can be easily and precisely attached to an animesh. They will be animated by the physical simulation and their attachment point will also be updated depending on the deformations of the animesh.
• I mentored Alexandru Voicu during its Google Summer of Code 2010 project on hair simulation and rendering. Thanks to his work, there is now a dedicated system to simulate hairs and fur. The motion of the hair strands are animated by the physical simulation, and the system has many properties to personalize the appearance of the hairs.
• A facial animation demo has been written, showing how to define facial expressions and control the animation of the morph targets to achieve the desired effect. This system would however need to be generalized into a more advanced solution, hopefully really soon.
• A motion capture facility has been written. The system is able to load animations from the BVH (Biovision Hierarchical data) file formats. A viewer (csmocapviewer) allows to visualize easily the content of the BVH file and the retargeting to a given animesh. The viewer is also shipped with a Point Light Display system, which has been designed to be used in psychology studies on the human perception of biological motion. It uses a Perlin noise to add points with random motion.
• Animeshes have been integrated in the "Project Bias" made by SueastSide. It is a demo of a medieval First Person Shooter, accessible as a demonstrator in CS (the 'csbias' application).
• The libnoise library has been integrated into CS (namespace CS::Noise). It is useful to generate coherent noise functions such as the Perlin noise, and can be used to generate and animate e.g. clouds or fire, but are also helpful for procedural animation of avatars (see the work on this by the master himself).

Future work

We will keep working on CS, CEL, and particularly the animeshes as part of the developments needed for the Immersive Virtual Environment. The main topics that are planned are:

• Hardware skinning pipeline and Level Of Details. These are the main missing functionalities in the current animeshes, but should hopefully be managed by our incoming developer.
• Custom animation channels, e.g. for morph or shader variable animation
• Artificial Intelligence: inclusion in CEL and interaction with CEL's behavior trees and path finding systems
• Assets management and edition tools
• Animation events system
• More advanced Finite State Machine animation node
• Playing with libnoise's inclusion in CS and Ken Perlin's ideas on using noise to add details in the animations
• Locomotion system and walking on uneven terrains
• More advanced animation retargeting
• Assets pipeline from the MakeHuman editor into the CS animeshes
• More clothes, props, and personalization of the animeshes

You ever been running so hard, you forgot why? You look down behind you and all you see is an empty alley. You slow down taking big steps as you come to halt feeling like a moron, leaning over and supporting your body with your hands on your knees. Desperately trying to breathe...
You hear screeching tires, two cones of light drift around the corner, blinding you. Your vampire movie obsession makes you duck as you hiss at the high beams.

I recently made a video for the GSoC YouTube channel.

I included all the main features the fur plugin support:

• Colliders
• Enabling / Disabling physics
• LOD
• Geometric properties
• Materials
• Diffuse Type
• Alpha / Color

Here is the video (hopefully you will be able to see it on the GSoC YouTube channel in no time):

Sometimes the need arises to monitor something.

How to install:

• Get the files from here. and place them in
  /home/youruser/vb/
• Make file executable: chmod +x /home/youruser/vb/virtualbox-applet.py
• Open virtualbox-applet.server and edit
  
<oaf_server iid="OAFIID:GNOME_VB_factory"
type="exe" location="/home/youruser/vb/virtualbox-applet.py">
...
to point to the right path.
• create a sym link in /usr/lib/bonobo/servers/
  
sudo ln -s /home/youruser/vb/virtualbox-applet.server /usr/lib/bonobo/servers/virtualbox-applet.server

• Right click a panel, click 'Add to panel', do a search on 'virtualbox', select 'Python VirtualBox Applet', click 'Add' and voila it should show up.

It seems to be a task that programmers by and large despise, but which is necessary nonetheless: Creating GUIs in the form of menus, buttons, the whole shebang. CS' GUI of choice is CEGUI. However, getting it to run is, right now (Oct. 18, 2010) is... troublesome.
First of all, you need a sufficiently current version, which means >= 0.7.0, which in turn means that the packages in the Ubuntu repositories are too old by far, so figuring out dependencies, installing them, checking out the SVN and building it yourself is the way to go:

apt-get install libtool libpcre3-dev
svn co https://crayzedsgui.svn.sourceforge.net/svnroot/crayzedsgui/cegui_mk2/branches/v0-7 cegui_mk2-0-7
cd cegui_mk2-0-7/
./configure --disable-xerces-c
make
sudo make install

So far, so good. But now we're getting to the Python bindings. If I were a little less curious than I am now, I'd say "It's not worth the hassle, just wait until they're officially supported" (which, for now, is scheduled for Nov. 19, 2010). Well, but I *am* that curious and hassled Kulik, so... You know what? Nevermind. Wait until they're officially released. The other way includes downloading bindings that are probably gonna change, writing build scripts yourself, all the good stuff. Just build CEGUI itself so you can enjoy CS' ceguitest and hairtest.

I managed to include diffuse reflection in the fur plugin, and now the lighting model is similar to Phong shading and the specular highlights are done either using Kajiya and Kay or Marschner shading models.

Here is a video of the results:

So, what is Crystal Space and what can it do for you?

Crystal Space is, centrally, a realtime 3D engine. In addition to that it includes everything that one needs to make a game or application; sound, keyboard, mouse and tons of other stuff. CS is event-driven, which means that once you've set up the map for playing, your code gets called each time something relevant happens.

To make juggling all that data easier, the Crystal Entity Layer (CEL) has been introduced. It adds the concepts of entities, property classes and messages. An entity is a "thing" in your game, the properties of which are determined by the property classes given to it. Property classes are, for example, pcmesh (which keeps the entities reference to a mesh), pctimer (which you can use to get a message either after a set delay or every frame), pccommandinput (keyboard and mouse input), pcmeshselect (which sends you a message when the user clicks on the pcmesh that the entity having this class also has) and so on.
Messages, lastly, are CELs mode of inter-entity communication. Property classes send messages to their entities when something relevant happens, and you can make your entities send messages to each other, too. Messages have a name and parameters, which are keys and values.
A somewhat deprecated concept is that entities also have behaviours. Those are the part of code that "receives" the messages, that is, gets called when a message with a name which is also the methods name in the code (I'm specifiaclly talking about writing behaviours in Python, but you can also do it in HTML) comes in, and is given the messages parameters. This concept is outdated only insofar as these message handlers now are encapsulated into "regular" property classes. So instead of having one and only one behaviour script per entity, you can now load and unload behaviour script property classes as you like.
Last, but not least, I also should mention entity templates. If you have multiple entities with are rather similar to each other, you can create a template from which those entities then are created.

To make things even easier (yes, that paragraph just now really was about how things get easier, not more complicated ;) ), CELstart was written. While all the defining templates, entities, meshes etc. can be done in map files, there still has to be a program that actually loads and runs those files. CELstart is that program. All it needs is a .zip file that includes your map files, artwork, whatever code you may have written and configuration files. It'll take those and start up the engine, load or create whatever you mentioned in celstart.cfg in your .zip, and off you go: Your game is running.

Well, that's the theory. All you have to do now is to think of a game or application that you want to write, then you find out what your entities are, then you assign property classes, model, texture and animate the models you want to use, write behaviour property classes and... Voila. Presto game.

Hi. My name is Sebastian, and if you visit the IRC channel #crystalspace on irc.freenode.net, you may know me as Baribal.
Somewhen around 2002 I heard of Crystal Space (CS) took a look. On my first try, the build process was frustrating enough for me to become discouraged. Every now and then I checked back and found new, shiny features. Also, each time I tried, I got a bit farther than before.
This time around I managed to set up everything that I need to get developing for real. Less than a month ago, I decided to create a chessboard with it; three years ago, I nearly managed to create a Go game using nothing but hand-edited XML and Python scripts. Now, three weeks after I looked at the first cube I made, I have both gathered a fundamental understanding of how to work with CS and wrote most of my chessboard. Considering that despite the hurdles I encountered on the way, I got quite far in a short time, I am wondering why not more people are developing games using CS, especially as nearly all the tools one could need are provided.
Then again building CS, then making the game are not trivial tasks, either, and most of the documentation meant to help along newcomers consists of the explained code of small applications. Personally, I can think of easier ways by which CS could be explained.
And that's why I asked for this blog.

Even though GSoC 2010 has ended, I still wanted to add some features to further improve the fur plugin, such as support for animating fur, and rendering fur with Kajiya and Kay shading model.

Presenting was once again Frankie the squirrel:

So, today is the last day of this year's Google Summmer of Code (although the date on the post will say it's August 17, it's still August 16 where I am =]). Time surely has flown by! I was really worried at the beginning of the program, there was a lot of code I had to get used to, and I still didn't know exactly how some things had to be done. But in the end, everything worked out, and I believe this project was a great success.

I was able to finish all the tasks that were on the original proposal, with minimal adaptations. I also documented everything as well as I could, both with comments in the code and posting the details in this blog. There are two demo applications as well, to show how the API should be used.

I would like to thank everyone from CrystalSpace for the opportunity, specially my mentor Andrew. People have been very helpful and friendly since our first contacts, during the GSoC applications period. I hope the code produced during this program can be put to good use.

Please feel free to contact me at anytime by mail. I will also stick around the IRC channel.

Best regards,
Leonardo

This last week I have made a few changes to the code, and I thought it would be good to make one post to talk a little about them.

First and most important, I found a problem with the demo application (not exactly a bug, more of a map misbehavior). If you plot a path going from the stairs in the basement01 sector to the basement03 sector, near the basement-dungeon sector, the path is likely to go below the stairs and through a wall. After careful examination, I realized this was actually caused by some parts of navigation meshes that were created below the stairs, due to the level geometry. Since Detour searches for the polygon nearest to the path's starting point, one of the polygons in this disconnected piece of mesh was being chosen, which caused the problem. In order to fix this, I altered the portal's polygon position for the portals that connect basement01 and basement03 in the world xml file, moving them up a little (the portal polygons were going below the stair level).
Here is the modified world file: link.

Second, I changed the DebugRender methods to return a list of csSimpleRenderMesh instead of drawing the structures directly using OpenGL. Notice that now you don't have to (read you shouldn't) call those methods every frame, only when the structure being drawn changes (you have to ask the iGraphics3D plugin to draw the meshes every frame, however).

Finally, I added another hotkey to the pathfindingtest application. Upon pressing 't', a path will be calculated between two predetermined points. This path will then be compared to a path previously calculated, and an error message will be displayed if they differ. If the paths are equal, nothing will happen.

The final GSoC deadline is tomorrow, or rather the firm ‘pencils down’ date, so I have decided to make a really short self-evaluation of the features I’ve managed to implement.

Done :

• Generate geometry – iFurMaterial (until the midterm)
• Animate geometry – iFurPhysicsControl (until the midterm)
• Write specific shaders – iFurStrandGenerator (until the midterm)
• External parameters – density and height maps, 3D textures, etc.
• LOD system and optimizations – iFurMesh inherits from iMeshObject
• Extend from hair to fur – thanks to Frankie the squirrel

There is still some code rearranging to be done, but nothing much, really: deciding what classes should inherit from what interfaces, making loaders and savers for the mesh, just better organizing the code.

I leave you with this footage of the CS fur plugin as it is now (the FPS is actually double than in the video and above 60 on release settings and ~30 FPS on debug):

Here's a video of my final results.

http://www.youtube.com/watch?v=dyMPjVtLIKM

Here are the latest improvements to the LOD system:

• Handling meshes with coincident vertices

In order to obtain really nice visuals adding texture support to the hair plugin was a must do.

However if we think about it, a hair mesh texture might have up to three dimensions, rather than just two. This is because hair strands can vary from root to tip (especially if you dye your hair) and can vary from strand to strand (like hair stripes). But having in mind that it is much easier to specify just a 2D texture (UV map of the base mesh) and extremely useful for fur, which don’t tend to vary from root to tip at all, I made two ways of defining textures for the fur plugin.

• 2D textures

For this type of textures only a UV map is needed, so fur strands will have the same color for the whole length of the strand. The color is of course equal to the value of the RGB pixel specified by the UV coordinates. Here is an example in CS of such a 2D texture used for Frankie (from Yo Frankie!):

• 3D textures

This is not a usage of 3D textures per se, but rather a simulation of using such textures. In order to keep things simple for the user, only two 2D textures have to be specified. A grayscale UV map that will be scaled from (0, 255) to (0, 1) and whose value will be used as the X coordinate of the second texture, while the Y coordinate is the length of the hair. An example of such textures for Krystal are:

Having the following result:

As you have probably seen from my previous YouTube videos, the FPS in the fur plugin isn’t quite real-time, but about ~10 FPS.

After doing some manual profiling (i.e. not using any profiling tool, but just commenting code and analyzing the average FPS in various situations), I came out with the following findings regarding the fur mesh plugin:

• Hair simulation

Number of Guide Hairs	0	50	100	200	367
Average FPS	46.07	37.70	32.63	24.76	18.76

Because I used Bullet ropes in order to simulate the physical model for guide hairs, I couldn’t really optimize the code to get better performance, so the only option was to generate as few Bullet ropes as possible, for the lowest LOD and also, not to many for the highest LOD setting.

This is why I made two types of guide hairs: pure guide hairs and LOD guide hairs. The pure guide hairs always have a Bullet rope attached, they represent the lowest LOD setting and grow on each vertex of the base mesh. On the other hand, LOD guide hairs are only synchronized with ropes at higher LOD, otherwise their position is updated just like for normal hair strands, using interpolation and barycentric coefficients.

So in order to have really good results, having a low poly mesh on which to grow fur is essential, and this can be done either by having a fake low poly mesh specified in the model file, or better yet, by obtaining a low poly mesh using the LOD system from another CS GSoC 2010 project, by Eduardo Poyart.

• Hair modeling

Number of Hair Strands	0	500	1000	2000	3670
Average FPS	49.34	31.56	23.12	15.41	10.53

When I collected this data for hair modeling I was using a genmesh to represent the fur geometry. The problem was that when I called functions to compute normals, tangents or binormals followed by a call to Invalidate() the FPS was really low for thousands of hair strands. However, I realized that I can easily compute all this data having in mind that the hair strands are created so they always face the camera. Furthermore, doing some C/C++ optimizations by increasing pointers, instead of iterating through vectors, gave some performance boost as well.

And of course, when the camera is situated further away from the fur mesh, having a low LOD setting, which draws fewer, thicker hair strands seemed a good idea. The only trick was to generate the hair strands in such a way that they always cover the base mesh (skull) and as they grow in number they give the impression of more dense hair.

• Hair rendering

Number of Hair Strands	0	500	1000	2000	3670
Average FPS	49.12	47.34	45.82	44.06	40.26

After testing the hair rendering data with both the Marschner implementation and a simple default CS Phong shader, I realized that the hair rendering didn’t need any more optimizations nor various LOD versions. The optimizations done by using lookup textures, as described in the Marschner Shader Part III post, provide good results by themselves.

• Overall

Number of Guide Hairs	0	50	100	200	367
Number of Hair Strands	0	500	1000	2000	3670
Average FPS (1024×768)	47.62	26.07	17.96	11.15	7.56
Average FPS (1440×900)	49.12	26.82	18.62	11.24	7.66

So, by making all of these optimizations and various LOD settings I managed to run the hairtest demo at a constant ~28 FPS at the lowest LOD and at ~15 FPS at the highest LOD setting.

Also, I realized that although sometimes a hair simulation will not be needed, animating the hair would still be a good idea, so I wrote an implementation of the iFurPhysicsControl that only updates guide hairs based on the base mesh movement, and also added the possibility to switch between various iFurPhysicsControl implementations on the fly. Not having Bullet ropes at all made the application run at ~37 FPS for the lowest LOD setting.

I have added a new parameter to the iCelNavMeshParams class, polygonSearchBox. Here is a detailed description (copied from the parameter values post):

"Before creating a path, Detour finds the closest polygons in the navigation mesh to the origin and destination points. This parameter determines the dimensions of the bounding box where Detour will look for the closest polygons. The bounding box is represented by two vertices: (center + polygonSearchBox) and (center - polygonSearchBox), where center is the point one wants to find the closest polygon to.

This parameter is also used to determine if a low level path that was calculated by Detour reaches it's intended destination (Detour always returns a path, either to the destination or the closest possible point). If the distance between the two points, in each of the coordinates, is less then this parameter, then they are considered to be close enough for this purpose."

One simple way to understand this parameter using the demo application is clicking on a point that is not exactly on the navigation mesh. For example, consider clicking on the walls: the greater the y coordinate of the polygonSearchBox, the higher you can click on the wall and still have the path traced.

The Recast and Detour toolset has a lot of parameters to set. In CEL's implementation, those parameters can be found on the iCelNavMeshParams class. But what values should be used for them? This post contains a very brief description of the parameters and a compilation of tips found either on the documentation for Recast and Detour or at Mikko's blog (http://digestingduck.blogspot.com, for some reason I can't link it here). Also, for more information, be sure to check the Recast and Detour discussion group.

• AgentHeight and AgentRadius: These values represent the bounding cylinder of an agent. For example, if we wanted to represent a human (using meters as unit), we could use AgentHeight=2.0 and AgentRadius=0.4.
• AgentMaxClimb: The height of the tallest step an agent can walk over. Following the previous example, we could use an approximate value of AgentMaxClimb=0.6 for a human.
• AgentMaxSlopeAngle: The maximum surface inclination where the agent can walk, in degrees. In our example, a value of 45.0 would be appropriate.
• CellSize: The size of the voxelization cell*. Smaller values give higher navigation mesh accuracy, at the expense of higher computation time. Good values generally range from AgentRadius/3 to AgentRadius/2.
• CellHeight: The height of the voxelization cell*. Smaller values give higher navigation mesh accuracy, at the expense of higher computation time. Generally, a good value is CellSize/2.
• MaxSimplificationError: When the rasterized areas are converted back to vectorized representation the MaxSimplificationError parameter describes how loosely the simplification is done (the simplification is Douglas-Peucker, so this value describes the max deviation in voxels). Good values are between 1.1-1.5 (1.3 usually yield good results). If the value is less, some strair-casing starts to appear at the edges and if it is more than that, the simplification starts to cut some corners.
• DetailSampleDist and DetailSampleMaxError: These parameters define how the navigation mesh is tesselated**. Sample points are generated inside the polygon. If the difference of height between one of those points and the height of the navmesh at that location is greater then DetailSampleDist, that point gets added to the mesh. DetailSampleMaxError controls the maximum allowed error when the mesh or poly outline is simplified. If both parameters are zero, the mesh won't be tessellated. For more details, look for the posts about "Navmesh Height Accuracy" on Mikko's blog.
• MaxEdgeLength: Maximum edge length for the navmesh polygons. A good value is something around eight times the agent radius in voxels (8 * (AgentRadius / CellSize)).
• MinRegionSize: Minimum isolated region size that is still kept after watershed partitioning***. A region is removed if the regionVoxelCount < minRegionSize * minRegionSize. The default value used in the SetSuggestedValues method is 20.
• MergeRegionSize: Maximum region size. The regions derived from watershed partitioning*** are merged. If regionVoxelCount > mergeRegionSize * mergeRegionSize, the region is not allowed to be merged with another region anymore. The default value used in the SetSuggestedValues method is 50.
• MaxVertsPerPoly: Maximum number of vertices per polygon of the navigation mesh.
• TileSize: Tile size****.
• BorderSize: Border size***** for the navigation mesh, in voxels. A good value is the agent radius in voxels, plus some padding ((agentRadius / cellSize) + 3).
• PolygonSearchBox: Before creating a path, Detour finds the closest polygons in the navigation mesh to the origin and destination points. This parameter determines the dimensions of the bounding box where Detour will look for the closest polygons. The bounding box is represented by two vertices: (center + polygonSearchBox) and (center - polygonSearchBox), where center is the point one wants to find the closest polygon to.
  This parameter is also used to determine if a low level path that was calculated by Detour reaches it's intended destination (Detour always returns a path, either to the destination or the closest possible point). If the distance between the two points, in each of the coordinates, is less then this parameter, then they are considered to be close enough for this purpose.

* - Recast calculates the walkable area of a map by voxelizing the triangles of the meshes that compose it.
** - At some point, the navigation mesh is tessellated in order to get more accurate values for the height.
*** - Watershed partitioning is used to group the walkable voxels and form the navmesh polygons.
**** - The navigation mesh is divided in tiles that can be rebuild, loaded or saved independently. We can, for example, update a navmesh to account for a dynamic object by changing only the tiles this object is into.
***** - Recast leaves a border about the size of the agent radius out of the navigation mesh, so it can guarantee any straight path cast inside the navmesh is valid, and the agent won't go through a wall when walking on it.

In order to help getting some initial results, the iCelNavMeshParams class has a method called SetSuggestedValues. This method receives as arguments the AgentHeight, AgentRadius and AgentMaxSlopeAngle, and either derives from that some initial values for the other parameters or gives them a default value. Using the values from this method may not generate a perfect navigation mesh, but will at least give a base to work on.

If some object changes position in a map, instead of rebuilding the whole navigation structure, one can update it using the iCelHNavStruct::Update() method. This method takes a bounding box and a pointer to a sector as parameters (although the sector is optional): the bounding box describes the area of the navigation mesh that one wishes to update, and the sector determines which sector should be updated. If no sector is specified, then the bounding box will be collided with each of the sectors navigation meshes' bounding boxes to determine what sectors have to be updated.

Note that this should probably not be used for objects that are on constant movement (npcs for example), since it's not very fast. This can be seen on the apppathfindingtest application by pressing 'y' (check last modifications to the demo application on this post).

Although updating a navigation structure takes some time, it is still way faster then rebuilding it.

In order to showcase the updating capabilities of the navigation structure, I have added a large stone block to the initial sector of the path finding demo application. This block moves linearly back and forth between two points near the stairs, and it is taken into account when building the navigation structure.

I also added some new hotkeys to this application, here is a description:

• '4' - Toggle stone block rendering.
• 'u' - Update the area of the navigation structure where the stone block is.
• 'y' - Toggle auto-updating for the area where the stone block is. When this is turned on, the navigation structure will be updated every frame.

Finally, after a lot of efforts and a lot of hardwork, lighter2 is able to produce caustics. Also a lot of bugfixes have been made in the original code, the major one being the one with lighting produced with the photons. The power of photons had to be scaled to match the illumination of raytracer, there is no need for that now.

Ok, enough of talking here is something pleasant for your eyes.

(This image was generated without any scaling of photons, and with only photon mapping enabled for direct as well as indirect lighting)

Now, regarding the intricacies of getting photon mapping working.

1.) Added a tag into the world file regarding the material, about whether it can produce caustics or not, also if it can produce caustic, what is the refractive index of the material. (For air the refractive index is considered to be 1, also if it is not mentioned for a caustic producing material, it is assumed to be 1. So, the caustics might not be that accurate, if one doesn't mention the refractive index.)

2.) While parsing the scene, the positions (Bounding spheres) of all the meshes which contain the material which can produce caustics are stored in a list. This list is used in the photon emission stage. The point light is considered to be like a spotlight which emits photons only in the direction of these meshes while emitting caustic photons.

3.) The photon tracing is facilitated with refracting these caustic photons, these photons are traced till the time they hit a diffuse surface, and instead of reflecting these photons in random direction they are refracted using simple laws of refraction (this is the point where refractive index is required).

4.) Finally in the final gathering stage it is not just the normal photon map which is used but also the caustic photon map.

(A lot of debugging and reworking also went into this process, which took all this time)

As for the future, I am trying to gt support for direction and spotlight lights for photon mapping and caustics, and also area lighting. I plan to get these working before the submission date for GSoC, and then it would be time for optimizing lighter2, in my opinion the memory optimization should be of higher priority than time optimization.

Although building navigation structures only take a couple of seconds (at least for the maps in CrystalSpace), it's important to be able to save and load them to/from files.

Since the navigation structures are composed of one navigation mesh for each sector and some extra information (like the name of the sectors contained in the navstruct and the high level graph), I decided the best way to save them was creating a zip file, containing one file for each navmesh and one file with some general information. These files are all serialized to XML.

To save each navmesh, the iCelNavMesh::SaveToFile() method is used. It receives as a parameter a iFile, which is where it will save the data to. To save navigation structures, iCelHNavStruct::SaveToFile() is used. This is the method that will probably be called by the user. It receives a pointer to the virtual file system and a char array as parameters, and will save the zip file in the current directory of the VFS, with the name described by the char array.

To load navigation structures, iCelHNavStrucBuilder::LoadHNavStruct() is used. It receives a pointer to the VFS and a file name, just like the SaveToFile method, and expects the file to be on the current directory of the iVFS received. It will open the zip file, read the main file and then call iCelNavMeshBuilder::LoadNavMesh() for each navigation mesh. It's important to notice that the load methods are in the builder classes, so the only way to create (either new or load) both navigation meshes and structures is from the builder classes.

In the demo application, loading the navigation mesh for the castle map is significantly faster then building it.

I created a new demo application to test the HPF algorithm (it's the pathfindingtest app). In this application, there is a player controled actor (Cally), which can be moved around by the arrow keys. The map used in this demo is the Castle map, from CrystalSpace.

Here is a list of hotkeys for this application:

• b: Build the navigation structure.
• l: Load a previously built navigation structure.
• s: Save the current navigation structure.
• c: Clear the navigation structure, as well as the current path, if there is one.
• 1: Toggle navigation structures debug rendering.
• 2: Toggle destination point debug rendering.
• 3: Toggle path debug rendering.

Once a navigation structure is either built or loaded, the mouse can be used to create paths. A left click will create a path between the actor's current position and the clicked position.

For the path following code, I used the pcmove.mover property, modified so the curves are sharp and precise instead of smooth. If the old smooth behaviour was used, there would be no guarantee that the actor would not walk out of the navigation meshes. The new behavior can be activated in any application that uses pcmove.mover, all that has to be done is set iPcMover::SetSmoothMovement() to false (the old behaviour is the default one).

I made a video of the actor moving around, being controled by the mouse, you can check it clicking here or in the image below (unfortunately, I was unnable to embed the video).

The basics of hierarchical pathfinding were already discussed in the post about the API (link). In this post, I'm going to talk a little about the implementation of HPF.

First of all, in order to build the high level graph that connects all portals, we needed a way to find a point that represents a portal. In the current implementation, the central point of the portal polygon was chosen. While this heuristic will give good results most of the time, it won't result in optimal paths. The difference in length to the shortest path possible will be more noticeable in a map that has very large portals. One alternative to reduce the effects of this problem is to create a number of points per portal proportional to it's size, relative to the agent size. However, while using more points per portal will result in more accurate paths, it will also cause a decrease in performance, so the number of points has to be chosen with care.

To find a path in the high level graph, we first need to add both the source and destination points to it, and then connect them to other nodes that share their sectors. We then calculate the path using A*. After the path is calculated, we remove the source and destination nodes from the graph, as well as any edges connected to them.

With the high level path calculated, it's time to refine it. For each two consecutive nodes in the high level path, we calculate a low level path segment using the Detour pathfinding. This step is done on demand: each time a user asks for the next node, either a new low level path segment is calculated or the next position of the current low level path is returned (if there is one).

In case the destination point is not reachable, the path to it's closest point in the navigation structure will be calculated.

In order to build a navigation mesh, all Recast needs are the triangles that form the meshes that compose the map. So, to build the navmesh for terrain meshes, I had to triangulate the terrain. This was done using the iTerrainSystem mesh interface. Meshes of this type have a collection of cells (iTerrainCell objects), which are further divided into a finer grid. These cells have a method for querying the height of the grid at a specific point (iTerrainCell::GetHeight()).

Once I had the grid size and a way to query the height, triangulating the terrain was trivial. The only thing that may cause some confusion are the triangle indices, since the terrain cells don't use the default coordinate system.

Here are a few screenshots of the navigation meshes built for the terrainf map, from CrystalSpace:

In this post I will explain how I managed to set some properties like length and density for the hair mesh.

The challenge here was to adapt a well-known technique and use it for these particular features. This technique consisted of UV maps, and was used for Krystal’s skull mesh (the picture from the left), whose UV map looks like this (in the right):

The length map

This is actually very similar to your usual heightmap, especially used for terrains and such, but it is UV mapped.

The data from this image is interpreted also similar to that of a heightmap, but it sets the length of the hair strands in that vicinity and not the height of the mesh, hence the name length map instead of density map.

And an example for a bangs hairstyle is the following UV map (left), having the result from right when applied to Krystal:

The density map

Although the density map looks similar to the other UV map, the length map, getting data from it, is done quite differently.

This is caused by the fact that data from this image is used to generate new data (geometry) as opposed to just refine existent geometry, which is the case with the length map.

Generating new geometry based on a UV map is also used in adaptive tessellation, but there the map used is a displacement map also having information about  the direction of the newly created meshes.

For this algorithm to work the mesh has to be composed of triangles and an UV density map has to be specified. The steps of the algorithm are as follows:

1. foreach triangle T in the mesh
2.   find the area A and density D of T
3.   if  D * A * factor > 1 then
4.     choose a point Y inside T using barycentric coordinates
5.     delete T and create 3 other triangles based on Y and T
   

The only things uncommon are choosing a point using barycenctric coordinates and finding out the density of a triangle based on an UV map. Regarding the barycentric coordinates you can check out one of my previous posts, where I also explained this technique when used to generate hair strands. Finding the density of a triangle based on the density map is not hard either, and I tried three ways of doing this, all based on the fact that UV coordinates are known for A, B and C, the points of triangle T.

• The average of A, B and C density

Although this approach evaluates just three points, it gives good enough results when there are plenty triangles to begin with and the UV map is at a lower resolution. Also applying a Gaussian filter on the image at the begging of the algorithm helps.

• The average of the density of the points situated on the Bresenham’s lines of triangle T

Actually I got to admit that this is not my idea, but I heard it from a colleague that used it for a real-time adaptive tessellation application. The main advantage of this approach is that it represents a compromise between speed and information analyzed. Also to improve this way of getting the density of a triangle convolution matrices can be used in order to obtain information from the vicinity of the currently analyzed point as well.

• The sum of all points density in the triangle T

Even though this might be the most obvious way to get the density of a triangle, generating all points inside of a triangle is not that easy. In order to do this I used the ever mentioned barycentric coordinates, but this time they weren’t generated random at all. Having in mind that the area of a triangle, which covers the whole surface of this polygon, is the base multiplied by height and divided by two, generating the first two barycentric coordinates along these lines seemed a good solution. The only problem is that the points further away from the base are analyzed more times (no division by two means passing points in this area more than one time), so doing this operation three times (one time for each base) and then getting the average, gives a very close approximation of the triangle density. Because I do this operation only at the begging I used this last method in the fur plugin implementation, being the best choice regarding the amount of information analyzed.

Next you can see Krystal having just a few hair strands on the top of her skull:

Other UV maps

UV maps can also be used to set various other information about a mesh, such as: the contour of a mesh, which vertices are more important or setting different materials/colors on different hair strands.

I already used UV maps to determine the contour of the geometry and to determine some pivots vertices (as guide ropes). Those pictures look like this, left is the contour:

I haven’t use UV maps to generate various colors for different hair strands, but I have in mind two approaches, and after implementing them I will write another post. However I think my next post will be about the LOD system for the fur plugin which is currently under development.

Dealing with non-welded meshes (meshes that have coincident vertices) is proving to be very tricky. Consider the case below.



In mesh A, the original mesh, vertices V1 and V2 are very close together, maybe even coincident, but they are not the same vertex. The same is true for pairs V3-V4 and V5-V6.

Let's assume the algorithm decides to collapse V3 to V5, for example. To get correct results, the result of that collapse should be mesh B. V4 has to collapse to V6 as well. If V4 doesn't collapse to V6, there will be a hole on the mesh.

With an usual mesh representation with vertices and triangles, aided by edges (pairs of vertices) and a list of incident triangles at each vertex, there's no information that tells us to collapse V4 to V6 when we collapse V3 to V5.

What extra information do we need?

In addition to our per-vertex list of incident triangles, we probably need a per-vertex list of other coincident vertices. When doing a collapse, we not only follow the list of incident triangles and work with them. We also need to follow the list of incident triangles from the coincident vertices.

Is that enough? Not yet, probably. We know our source and destination vertices, V3 and V5. When we jump to V4 and process it, we need to know that we need to collapse V4 to V6, not V4 to V5.

What else do we need? What if V5 is coincident with V6 and a third vertex, V7? How do we know we need V6 and not V7?

I leave the answer as an exercise to the reader. I don't know it myself, at this point.

Ah, the joys of computational geometry!