December 22, 2009 by Mark.

Rendering efficiently is one of those topics that is widely spoken about in the world of 3D graphics. Asking a question like ‘What is the best way to render a bunch of Objects’ is as open ended as asking ‘What is the best way to cook chicken soup.’ It is all based on application and preference and in all likelihood, there is no universal answer to this question. However, there are a series of specific solutions to this problem that can help in creating a mechanism that is best for the particular situation.

My problem is rather generic and will require a generic solution. I have a bunch of objects that need to be sorted by certain criteria in order to minimize state changes. It has to also support Shaders (Cg in my case) and it should minimize Shader state change between object rendering. Furthermore, an object must be generic enough to support complex models with bones and animations. On top of that, it should be easy to use. To start, we might need to break this down into smaller parts.

Objects:
For the time being, lets refer to an Object as a list of vertices inside a vertex buffer. It may or may not be accompanied by an index buffer, but in most cases it will. This Object will be shuffled to the graphics card to be rendered for each Object that exists in our world. This is inevitable until we support something complex like hardware based instancing.

State Changes:
Unless you want all objects to be rendered in the same way, in the same spot, and with the same vertices, you probably want some sort of state change. A state change is a change in any part of the system, whether it is the position of the camera, a new Object to be drawn, or a new effect. To quantify a state change, it is best to organize it into the types of state changes: swapping Render Targets, Shaders, Technique, Shader parameters, and using a different vertex or index buffer to draw an object. The order of the state changes, as listed above, matters because the changes at the beginning of the list are the most expensive and the changes at the end of the list are least expensive.

The RenderGraphNode:
This is a generic interface to which many types of nodes will be derived from. Each derivation of the node will be the embodiment of the changes listed above. In addition to the state change, the node will also be a container for child nodes. Usually the node will be generic enough to contain any type of node. However, in our case, we want to preserve an order to our nodes so that we optimize the state changes. The root of our tree will be a change in Render Targets. For the most part, there will only be one Render Target, the backbuffer (our screen). When a child node is added, it will automatically be sorted into the correct place in order to minimize the state change. This is especially important for Shader parameter changes because there can be multiple parameters in one Shader.

The RenderGraph:
In order to encapsulate all this, I need a class that will be the owner of Render Targets. It will be the only thing passed into the Renderer for drawing. At that point it will traverse the tree and render.

Sounds simple right? Yeah, but something doesn’t feel good about this design.

If we leave the design at this point, we are left with a bunch of nodes in which the user has to put together. This design is acceptable by some. In fact, OpenSceneGraph uses such a design for its SceneGraph. It is a bunch of classes that fit together in a tree fashion. Throw in a Visitor pattern into the mix for easy iteration and you have an engine. I’m not quite as happy with that design as my OpenSceneGraph counterparts are. The problem is, in my eyes, that it’s very verbose. Putting together a simple scene with an airplane in it was quite lengthy. You have to add a GeometryNode to a TechniqueNode to a ShaderNode to a RenderingTarget, and so on.

So back to my original question, what is the best way to implement something like this? When I figure it out, I’ll write about it.

Posted in Radiant, 3D Stuff, C/C++, Stuff | No Comments »

December 3, 2009 by Mark.

I’m converting my blog to something a bit more useful. My long rants about my game engine were all leading towards a game of some sort. In the process I have recruited a friend to help me realize that dream. So, give a kind welcome to Alex.

Our first title will be a strategy turned-based war game by the name of ‘The Mortal Realm.’ It will feature my 3D engine and a robust battle system. As far as complexity goes, this game is one of the simplest we have come up with. It’s a simple point and click style of game with very minimal artwork. I’m hoping it will be a great test bed for my engine as well as Alex’s AI.

Posted in The Mortal Realm, Radiant, 3D Stuff, C/C++, Stuff | No Comments »

March 26, 2009 by Mark.

I’ve been diligently working on a scene partitioning system which combines an Octree with a Uniform Grid. Basically, the way it works is that you build a loose Octree, which starts 4 levels deep. When each node reaches a critical mass, it subdivides into another level. The max levels you can have (While still being optimal) is 7. So, let’s assume that we have a detailed scene with a 7 level Octree. At the bottom of the Octree, each node is 128th the size of the entire area you are encompassing and it is also uniformly proportional to the entire area. You can build a Uniform Grid out of the bottom most nodes giving you the best of both worlds.

When all this is built, to add and remove items from the grid is a matter of doing simple division of finding out the exact spot in the Uniform Grid where the object belongs. Since pointers are being shared between Octree Nodes and Uniform Grid Nodes, you essentially add an item to the Octree in O(1) time (Adding to a Tree structure usually Takes O(Log n) time). Collision detection with simple objects is O(1) time while with complex objects it is O(Log n) time. What I have done is made the Octree a bit faster in some areas. Good idea, isn’t it?

Here is my problem. While randomly googling on this topic, I found a patent for this idea. The patent is very similar to what I just described. What I want to know (For all you Law junkies out there) is how does this effect me? Can I get sued? Does it matter that my implementation is my own and not copied from the patent? Does it matter that my implementation is Open Source? Are there ways to get around this patent (My implementation is different but algorithmically similar)?

Any suggestions are welcome.

Posted in Radiant, Open Source, 3D Stuff, C/C++, Stuff | No Comments »

November 10, 2008 by Mark.

I held a bet with my brother to see who can guess the number of lines of code (or at least, close to it) my rendering engine is comprised of. Neither of us were close but I got a good sense of how much work went into this giant mash of code. About 25,000 lines is the total. That total is comprised of approximately 12,000 lines of computational code and about 13,000 lines of comments. This number does not include blank lines and such things. Regardless, it’s a staggering number for a project that is being worked on by one person, part time.

The engine itself is about 45% complete, with the majority of planning done. One of the components, my math module (it handles math stuffs and collision detection), is finally finished. I can breath a sigh of relief, it’s not easy stuff. Unfortunately I didn’t write any unit tests for it so I don’t know if it actually works or not. The project is open source. So, if anyone is masochistic enough to write a tests for my math module, by all means :).

Posted in Radiant, 3D Stuff, C/C++, Stuff, win32 | No Comments »

September 7, 2008 by Mark.

I finished writing my own Thread Pool subsystem and then put it through its paces. The results are obviously not that shocking because anything that is multi threaded is more efficient on dual core machines. The machine I was running it on has a AMD Turion 64 X2 CPU and sports two 2.0Ghz cores. It’s not the best machine but its quite speedy for what it is.

Anyway, as I mentioned in the previous entry, threads are great and run best when they have a dedicated core. When there are more threads then cores, the OS then has to time-slice in order to give the threads equal time on the CPU. Having a dual core machine, the optimal amount of threads that I can handle is 2. The following is a graph of the time it took to process 50,000 square root calculations, 100 times in succession:

On the first run, I did not use any threads. Rather, I let the calculations run in sequential order on the main process. The blue bar represents the thread priority at normal and the purple bar represents the thread priority at Highest. I did this in order to measure the speed difference between the normal and highest priority setting. I should also note that even though the thread priority can be manipulated, it is up to the OS to enforce that. In some cases the OS may decide not to enforce the request for higher priority and give the processing power to other threads.

The second and subsequent runs were using the Thread Pool with an increasing allotment of threads. Each 50,000 calculations were plugged into its own Job and sent off to a worker thread. Having only one thread was not much of a boost over a single process (Took about 1920ms). The main process was put to sleep using the WaitForSingleObject() function call while the worker thread did the processing. At two threads there is a massive increase in time. Just as one would assume, the amount of work was spread over two cores and the time it took to process it all was cut in half (About 950ms). This is the optimal amount of work my CPU can handle because each thread has a dedicated CPU core. Increasing the amount of threads actually increased the amount of time it took to process the calculations. The reason being is that the OS had to time-slice the different threads on both cores. The time increased by about 20ms each time I increased the number of threads.

Thread Pools are very efficient at what they do. As mentioned in the previous entry, creating a thread and destroying a thread could have increased the amount of time required to process a batch of 100 calculations. Regardless, the work I done is Open Source and as is my engine. You can download it here (I’m not responsible for unexplained fires, deaths, or alien abductions due to using this code).

Posted in Radiant, Open Source, 3D Stuff, C/C++, win32 | No Comments »

September 5, 2008 by Mark.

I have been passively researching multicore processing for the last few weeks and I came to the conclusion that it is rather easy to implement. In its simplest form, all you need to do is create threads and have them do Jobs. The OS will then schedule a thread to be run on a dedicated core. Having multiple cores makes those threads run at the same time as opposed to the old time-slicing method of single core processors. But, at the very base level, it’s rather primitive and can actually be improved upon.

Creating threads and closing them is fairly fast but may be a bottle neck if the engine does that consistently. The best way to handle this is to not do it, obviously. This is where a Thread Pool comes in handy. It creates a bunch of worker threads that don’t get destroyed until the program exits. Each thread will sit idle until a job has been passed into it to be processed. This involves the use of critical sections and semaphores to accomplish and is much faster then allocating and deallocating threads. A critical section is optimized for speed as compared to any other form of asynchronous data sharing and messaging (alternatives include Mutexes, Events, and so forth). The rule of thumb is to create enough threads so that the OS does not have to time-slice. This is usually done by allocating [num of cores] + 1 threads.

In order for a Thread Pool to work properly, it requires a few things. Firstly, a Job queue. This is a long list of jobs that will get distributed between the threads once threads become available. Secondly, some sort of thread state management. It includes a set of states that the threads can be at. The basic types are ‘Working’ and ‘Idle’, but it can vary on the amount of complexity you add to the Thread Pool. Lastly, it requires data sharing. I suggest writing an object that wraps data around a locking/unlocking mechanism (Semaphores come in handy for this task). Once these aspects are implemented, the Thread Pool is basically finished.

Usage is another key role. Lets assume that you either use the built in Win32 Threading pool or roll your own, it doesn’t matter which one you do. Furthermore, you have some very repetitive code that you want to multithread. If you don’t quite know what is multithreadable, the best place to start looking is in any for loop. The place where I’m going to use my Thread Pool is in a loop where I would have to update some world object, such as a player state or even scene management. For example, this loop might call your world object and cause it to return collision information with its nearest neighbors. Plug the world objects into the Thread Pool, have it run asynchronously and output some data into some shared object. As it’s doing this, have the main thread wait or do some other processing until the output is realized. Once its all done, the Thread Pool will suspend its threads and the main thread can resume doing its job.

What this Thread Pool is designed to do is to complete small tasks asynchronously. Sticking a dedicated piece of code on one thread (such as a sound subsystem, or networking) is rather counter productive to a Thread Pool because it utilizes the thread until the end of the program. I would suggest that a subsystem that is substantially heavy be on a separately spawned thread instead. Another word of advice that I came across is to keep the amount of writing done on each thread to a minimum because it requires locks. The best approach is to have each thread write to its own dedicated memory that is attached to the Job that its processing. Keep the shared data read only when possible.

I’m in the process of implementing my own Thread Pool and once its done, I’ll post some metrics.

Posted in 3D Stuff, C/C++, Stuff, win32 | No Comments »

May 20, 2008 by Mark.

Alright, I ended my zealous trek through the inner workings of SIMD just because I wasn’t using it enough in my project. Don’t get me wrong, its a really nice piece of technology to dabble in, especially when doing math on a large scale (say, Matrices). But for the day-to-day programmer in me, I really don’t get to use it as much as you might think.

But, I’ve done some detective work and most compilers nowadays optimize the code in such a way that SIMD gets incorporated automatically. Therefore, learning SIMD should be put in the same category as learning Assembly. Its nice to have but in reality it will be rarely used, if ever. I have a feeling that I’ll run into a situation where SIMD is required and its the only thing that can save the world from total destruction. Well, until then, I’ll just shelve it.

On the bright side, I finally gave my game/rendering engine a real name: ‘Radiant.’ I don’t know why I named it that, and for some reason, I never second guessed it. It was one of those spur of the moments that I hit F2 and started typing. Don’t ask me what or why, I’m still in the wilderness on that one. Anyway, progress on the engine is a bit slow just because the only time I get to work on is during bus trips to and from Hamilton, or other places. If there were more hours in the day, I could actually get something done.

I should also say that I’ve re-worked the way the engine is laid out because all my singletons were not working well with DLLs (I think I wrote about that, somewhere). This quickly because a mess. SVN likes things to be done in order and in small chunks, else it starts bugging you about cleaning up the repository. I like to do things in big chunks, literally taking a +1 Battle Axe to the tree and then rebuilding it from scratch. Bad tactic, I know. Lets just say, SVN was in pain. Poor thing.

As a side note, I found out something interesting today about the MSVC build system; It supports multi-core compilation! Its like your own distributed build but on your own machine, Hooray. More on this later.

Posted in Radiant, Open Source, 3D Stuff, C/C++ | No Comments »

March 26, 2008 by Mark.

I’ve been scouring the internet for some decent resources on math, collision detection, and physics, so here are some:

• Essential Math
• Game Physics Resources
• Real-Time Collision Detection
• Advanced Character Physics
• Simple Math Primer
• Flipcode’s Articles
• Harvey Cartel’s Collision Detection Site (Thanks Miksago)
  

More to come, later.

Posted in Radiant, 3D Stuff, C/C++, Stuff, Uncategorized | 1 Comment »

March 24, 2008 by Mark.

With all the craziness that last weekend brought, one of which was a book I ordered from Amazon. Just like the title says its a book about collision detection within 2D and 3D environments. It’s a bit on the expensive side, about $50, but its worth every penny. I had a chance to read the first 5 chapters on Sunday. It started off with a quick math primer and then dove head first into how collision detection works. It has a few chapters on bounding volumes and space partitioning; the two topics I have been obsessing over for the last few weeks.

Possibly the best thing about this book when compared to my other math books is that it explains the concepts with code, more then with math. For most programmers, this is a godsend. Reading a few lines of code is much easier (at least, for myself) then trying to comprehend or remember mathematical symbols.

Regardless, If you’re building an engine of some sort (Graphical, Physics, etc), this book is definitely an asset. Collision detection is not only used in physics engines, it is the core functionality of Octrees and Scene Management. Ergo, it is an integral part of an engine. Although, I don’t recommend this book to novices, or people that do not have any 3D engine building knowledge under their belt. It is Math and Algorithm heavy and requires substantial engine design theory.

EDIT: Looking through some of the supplementary books from the Morgan Kaufmann series, they all seem very interesting. If those books are of the same quality as the Real-Time Collision Detection book, then this entires series of books will end up on my bookshelf very soon. It’s something to be desired.

Posted in 3D Stuff, C/C++, Stuff | No Comments »

March 17, 2008 by Mark.

I have been working on my game engine (Which still does not have a name; Suggestions are appreciated) for a while now. It has seen its share of refactors ever since I started on it back in 2006. But recently, I have come to a fork in the road. I am overwhelmed with the amount of things that I need to keep track of which makes me second guess some of my design decisions that I have made. One of which, is weather or not to write my own scenegraph or to use a stock one, say, OpenSceneGraph.

From experience, I can tell you that the amount of time that it would require to learn, implement, and test OSG’s implementation would be comparable to the amount of time it would take me to write one from scratch. I have been plagued with these sorts of decisions ever since I started the rewrite of my code. The benefits of using a library over writing your own can only be determined by the ease of use of the library. For example, if its easy to build, incorporate and debug then it probably is better to choose it then to write one from scratch. In the case of OSG, the library is big. No, its Massive!

I am still not convinced that OSG would be worth using over my own implementation, simply because of the learning curve and the work required to properly incorporate it into my engine. I would literally have to wrap my engine around OSG, rather then have it work symbiotically. That just does not sit well with me. Regardless, I will still poke around inside OSG and learn how their scenegraph implementation works.

Where is my trusty Bearded Axe, its time for some hacking!

Posted in Radiant, Open Source, 3D Stuff, C/C++, Stuff | No Comments »