All Blog Entries

All blog entries, ordered from most recent. Entry count: 1198.

Pages: 1 ... 63 64 65 66 67 ... 150

# What is GUID and how to use it

Thu
16
Jul 2009

There are many ways to identify objects in a collection. One of them is to keep direct pointers to objects. Another way is to simply index their positions in an array. We can make user see only some strange indirect "handles" without any obvious meaning, like HWND or FILE*. We can also give objects string names or some numeric identifiers. SQL databases often use integer number to identify record in a table and new identifiers are generated as subsequent numbers. Another solution is to use GUIDs.

GUID means Globally Unique Identifier and it is a kind of general purpose, 128-bit numeric identifier. GUIDs are generated from some random data. We can be sure about their uniqueness in any context because of their size, as 2^128 possible values is more than stars in the whole observable universe :) That's why they are called "globally unique".

We could just generate 128 bits of data from any good pseudorandom number generator and call it good identifiers, but to standardize this idea, they have created standard - RFC4122 (it's actually UUID, but let's ignore the difference). This standard says how to express GUIDs as strings, made of hexadecimal numbers separated by dashes (for example "f81d4fae-7dec-11d0-a765-00a0c91e6bf6"). You can find such GUIDs everywhere. For example, run "regedit.exe" and look into key HKEY_CLASSES_ROOT\CLSID or run your Visual C++ and run command Tools / Create GUID from the main menu.

The standard also defines bit structure of the UUID and algorithms to generate it. There are several possible algorithms. Some of them use system time or even network card MAC address. The simplest one is version 4 algorithm, which uses only random number generator. Some of bits have special meaning and code algorithm which have been used to generate particular GUID.

Here is my code in C++ defining GUID structure and the algorithm to generate it.

Comments | #c++ #algorithms Share

# Efficient Finding of Duplicated Files

Tue
14
Jul 2009

I've recently wrote a tool for finding duplicated files in a given directory. I wanted to do it efficiently and here is my algoritm.

My basic idea is to first recursively enumerate all files in the directory and its subdirectories and sort their descriptions by file size. Making it this way, we can then iterate through this list and for each file look ahead to see how many other files have same size. If two files have different sizes, they are obviously not equal in terms of their content. So if there is only one file with particular size, it can just be skipped. If there are two files with same size, we must just compare them by content.

If there are many files with same size, things become more complicated, as any possible combinations of them can turn out to be identical. My solution is to compare two files by a "header" (lets say - first 1024 bytes) and if they are equal - by MD5 checksum of their whole content. Checksum of each file is lazy evaluated, so it's calculated only once, the first time its needed.

As I iterate through the sorted file list, I mark reported files not to process them again. I can do it because I ensure that if a file is reported, all other identical files are also already reported. In my real code I do the same with files I encounter errors with, but here I wanted to simplify the code.

Comments | #algorithms #winapi Share

# Cascaded Shadow Mapping

Sun
12
Jul 2009

When I was writing The Final Quest engine for my master thesis, I didn't manage to implement any technique to ensure good quality shadows in outdoor scenes. I've read about all these kinds of perspective reparametrization like PSM (Perspective Shadow Maps), LiSPSM (Light-Space Perspective Shadow Maps), TSM (Trapezoidal Shadow Maps) or XPSM (Extended Perspective Shadow Maps) and all that math behind them seemed very scary to me. Today I know that complexity of these techniques also causes some artifacts in particular cases and commercial games more often use simpler technique called CSM (Cascaded Shadow Maps).

Yesterday I've implemented CSM and I'm very glad with the results. Of course there are always some artifacts, aliasing problems and z-acne on some distant objects under particular surface angles, performance degradation (additional objects rendering to 3 x 1024 x 1024 textures must take some time) etc., but still its the first time I have not so bad outdoor shadows in my code. On the screenshot below you can see transitions between cascades marked with red arrows.

Comments | #directx #rendering Share

# KD-Tree

Thu
09
Jul 2009

People at forums are usually advised to learn BSP, quadtree or octree as space partitioning data structure, but there are many more interesting structures than these three. This time my choice for home project is KD-tree. It's actually something between BSP and octree. Just like BSP it's a binary tree (each non-leaf node has two child nodes) and optimal splitting plane is estimated each time by special algorithm, but splitting planes are always aligned to one of three main axes and thus each node can be described by an AABB (axis-aligned bounding box), just like in octree.

As my tree is designed to manage objects and not geometry, nothing can be split and some of objects may intersect splitting planes. How to deal with them? I simply assign them to the parent node, so not only leaves are allowed to contain list of objects. To avoid too many small objects intersecting splitting planes to degrade performance by falling into top level nodes (it's called "sticky planes" or something like that :) I adopted "loose octree" idea to my KD-tree. It simply means I extend each node’s bounding box so that each node's children slightly overlap each other and small objects intersecting splitting plane fall into one of the children.

My KD-tree is also dynamic, which means it reorganizes itself as objects get added, removed and moved in the tree. It's actually quite simple. Each time an object is added to a node, that node can be split into two children if it's object number exceeds constant limit. Similarly node can be merged by deleting it's children each time an object is removed from one of its children, if the number of objects in that node and its children drops under constant minimum.

For additional performance, I allocate tree nodes from my own "Free List" memory pool and I keep objects connected to each node as doubly-linked list.

I also came up with an idea how to easily visualize quality of my space partitioning technique. I keep track of the number of tree nodes and objects on each depth level. This way I can tell from these several numbers whether tree is more "tall" or "wide" and whether most of objects stay in leaves instead of some top-level nodes.

Here are some screenshots and a video from my recent code:

Comments | #rendering #video #gallery #algorithms #math Share

# Computer Self-Defense for Beginners

Sat
04
Jul 2009

Inspired by recent virus-infestation of one of my family member's computer I've decided to write a small guide to computer self-defense for beginners - that is, to write down things that are obvious for every computer scientist, but not for every user. I emphasize I'm not a security specialist so for some of you my thoughts may look lame :)

Historical background: Many years ago people used to copy programs and transfer them between computers using floppy disks. Viruses were infecting EXE files by adding their code to programs and once someone ran such file, the virus spread to other programs in his computer. Viruses were sometimes written for fun. Some of them were harmless, while other did "pranks" such as formatting whole hard drive :) Now we live in the Internet era and programs downloaded from the Web or from CD/DVD disks require installation, so viruses like these are no longer effective.

Today's viruses are no longer infecting particular EXE files. They are rather kind of worms or trojan horses (however you call or classify them) - they just install themselves in Windows and run in the background as separate programs. They are neither destroying whole computer nor totally harmless. Modern malware software is part or organized crime, so it can, for example, steal user's passwords to online bank account, MMORPG game or use his computer to perform DDOS attacks and sending spam.

So how (not) to catch a virus? Viruses are not usually able to infect a computer without user's initiative. It's quite safe to use Windows, be connected to the Internet, browse any websites, read any emails, open any files such as music (like MP3), images (like JPG), archives (like ZIP) or documents (like PDF). The exception is when one of the programs have a bug which can be exploited to execute code embedded into document's data. Such critical security bugs are fixed quickly so the security procedure for them is to update your software regularly - use Windows Update / Microsoft Update and install new versions of programs you use, especially these connecting to the Internet.

The only possibility when a virus can run without user's approval is Autoplay technology for flash drives and CD/DVD disks. Each time you enter such media, Windows looks for autorun.inf file and can automatically run prepared program. As pendrives are very popular nowadays, I consider critical for computer security to turn off the Autoplay functionality. You can do it using free Tweak UI tool, just like that:

It's amazing to me how some people constantly suffer from viruses on their computers while other almost never catch any. Do the second never visit porn sites or use cracks and pirated software? Maybe, but I think it's rather the matter of obeying some simple security rules. Websites, emails or image/music/document files are not able to run arbitrary code on your computer. You must explicitly agree for that. This danger comes in two forms. First one is when a website wants to run/install something on your computer, usually using ActiveX technology. You can see warning about that asking if you really want to allow the website to run such program. Virus installs itself on your computer only if you agree to that.

The second danger is when you just run new EXE file. How to distinguish between safe and dangerous executables? First of all, never run unknown EXE files just for fun. Never trust it's a new brilliant porn screensaver, good and free antivirus software or a document in executable form (like image gallery, video, ebook, archive), even if you have it from your best friend. Pirated software and cracks/keygens from P2P networks also very often contain viruses. On the other hand, you can be almost sure it's safe when you download a well-known application from its author website or a website such as SourceForge.net. If you are not sure about an executable file and you really need to run it, scan it with an antivirus first.

I believe these simple rules are worth much more than not using Windows, Internet Explorer, Outlook Express or cracks/pirated software and using any firewall or resident antivirus protection.

Comments | #windows #software Share

# Thoughts on Display Settings

Tue
23
Jun 2009

I've decided to make a demo for this year's Riverwash demoscene party. For that purpose recently I've prepared my framework and coded loading of display settings from either command line parameters, configuration file or my brand new dialog box:

Coding it reminded me of my thoughts about display settings from user's versus programmer's perspective. User is usually able to change screen resolution and sometimes also change refresh rate, turn vertical synchronization on/off, toggle between fullsreen and windowed mode, choose antialiasting, texture filtering quality and some general quality/performance parameters. On the other hand, programmer passes bunch of parameters to Direct3D as D3DDPRESENT_PARAMETERS structure and other arguments to functions CreateDevice and Reset. The question is how to map between these parameters?

Here are my current beliefs on this subject:

[+] Adapter: I just pass D3DADAPTER_DEFAULT constant. Sure it would be better to give a choice of an adapter (one can enumerate adapters using IDirect3D9 methods), but it's useful only on multi-monitor systems and not many games expose such setting.

[+] DeviceType: I always pass D3DDEVTYPE_HAL. Using software reference rasterizer D3DDEVTYPE_REF makes no sense, as it gives SPF instead of FPS :)

[+] BehaviorFlags: Now I always pass D3DCREATE_HARDWARE_VERTEXPROCESSING. Using software or mixed verex processing made sense only on old hardware, especially on old Intel laptop graphics chips, which had Pixel Shader 2.0 but no Vertex Shader at all.

[+] BackBufferWidth, BackBufferHeight: I give a choice of display modes available on default adapter with format hardcoded as constant (D3DFMT_X8R8G8B8). One can enumerate available display modes using IDirect3D9 methods. In windowed mode it could also be reasonable to be able to set any given resolution (Width and Height as text fields), as well as manually resize application's window.

[+] BackBufferFormat: I just use D3DFMT_A8R8G8B8. Choice between X8R8G8B8 and A8R8G8B8 just the matter of having additional fourth channel available (alpha), which is obviously not visible, but can be written, used in alpha blending and thus utilized to do some special effects (like masking intensity of some effect in screen space).

[+] BackBufferCount: I just give 0 here, which resolves to default value of 1 back buffer. I'm aware that using value 2 can change the way rendering is performed a bit.

[+] SwapEffect: I always use constant D3DSWAPEFFECT_DISCARD, as it is the fastest one. It says that entire content of the back buffer can be discarded after frame was presented and program have to render new frame from scratch (which is what we always do in game development).

[+] AutoDepthStencilFormat: Direct3D defines many of them, but for real all the D3D9 generation hardware supports only three: D3DFMT_D16, D24X8 and D24S8. So the choice is only based on the decision whether we need higher, 24-bit precision or stencil buffer.

[+] Flags: For the best performance possible I always give D3DPRESENTFLAG_DISCARD_DEPTHSTENCIL and never give D3DPRESENTFLAG_LOCKABLE_BACKBUFFER.

[+] FullScreen_RefreshRateInHz: Nowadays, when many (most?) people have LCD displays, standard refresh rate is 60 Hz and maybe 75 Hz. In the CRT era setting good refresh rate was crucial for playing comfort and thus it was very annoying when a game didn't expose setting of refresh rate, but used default 60 Hz instead. I believe refresh rates should be enumerated and given as a choice next to the resolution.

[+] PresentationInterval: This is the value the "VSync" setting is converted to. It looks like D3DPRESENT_INTERVAL_DEFAULT behaves as VSync turned on (FPS <= RefreshRate) and D3DPRESENT_INTERVAL_IMMEDIATE means VSync off (FPS as high as possible), but once during my experiments I've observed that flag D3DPRESENT_INTERVAL_ONE behaves slightly different than D3DPRESENT_INTERVAL_DEFAULT (I can't remember the details now).

I know I would sound more "professional" if I considered all other constant values available and their possible uses, but I don't care :) My point here was to simplify the problem to be able to map these technical parameters to the display settings exposed to the user. Multisampling is separate subject so I don't cover it here.

Comments | #demoscene #directx #rendering Share

# New Web Browsers: Safari 4 and Opera Unite

Sun
21
Jun 2009

Two new web browser applications have been released recently: Opera Unite and Safari 4. Of course they are both free. Here is my quick review.

Starting with the second one, I must admit I've never used Safari before. I generally dislike Apple corporation, but today I read news about new Safari 4 and decided to try it on my laptop.

My general impression is rather good. The browser's look and feel is quite standard comparing to other popular programs of this kind (Internet Explorer, Firefox, Opera). The same applies to keyboard shortcuts and set of features. All websites I tried work OK in Safari. To make long story short - Safari is yet another web browser, not bad but also not so special.

There is one (not so) small issue though. For all of you who complain about performance and memory consumption of Firefox: try Safari or just look at the screenshot below and you will change your mind :) I just entered one website (www.onet.pl) on both browsers.

Now let me say few words about Opera Unite. I tried Opera before and my impressions were very positive (although I still use Firefox). Personally I think Opera is a very good web browser - it launches and runs very fast, has lots of features and its GUI is nice. This time I just wanted to test brand new functionality introduced to Opera Unite - a personal web server.

To set up your own server, you just need to click on a command in Opera menu. Then you have to create an account in Opera system (standard question about your login + password + email). According to current trends in Internet applications (like Skype or Hamachi), there is no or minimum technical configuration required. Opera proposes use of UPnP (to forward ports through router) and automatically sets up something like dynamic DNS in operaunite.com domain.

Not only is the server setup far from what you have to do to install and configure Apache server, but sharing files is so easy too. You just need to point to a directory on your hard disk and it automatically gets shared, so people can explore directories and download files if they know correct URL (for example, the URL for my test was http://reg-laptop.reg01.operaunite.com/file_sharing/). I think I don't have to add that there is no need to code or setup any CMS script to make it work. You just put your files and a nice website for browsing them is generated automatically.

There are also some other "services" available. Photo Sharing works just like File Sharing, but looks like a gallery, where user can see image thumbnails instead of list of files. Fridge allows you and other people to leave sticky notes on your virtual fridge :) The Lounge is a chat service. Finally, Web Server is a normal server where you can put your own website starting from index.html. It looks like Opera Unite supports only HTML, without any PHP, MySQL or other stuff like this.

Opera Unite really impressed me. I've never seen anything like this before and now I think it will cause kind of a small revolution in the Web. Internet have always been server-oriented and transferring/sharing files between regular users always have been an issue. Of course Opera Unite is not going to replace traditional website hosting services (most of home computers do not work 24/7), but it can greatly support exchanging files between people.

Comments | #web #software Share

# ASCII Art in Pixel Shader

Thu
18
Jun 2009

Today I'm going to show completely ugly and useless effect :) I have always been fascinated with ASCII art, so I'm glad I am now able to visualize it on GPU. Here is the final effect:

And here is how I've made it. First, I took a 3D scene with some untextured boxes.

Now I do pixelate effect to have my image looking like each 8 x 8 pixel group have same color. Optimally I should render whole scene into 8 x 8 times smaller render target and rewrite it with POINT filtering, but currently I'm just doing some processing during rewriting this image from render target texture to the back buffer. That processing is simply rounding texture coordinate down to a multiply of 8 texels:

// in float2 TexCoord : TEXCOORD0
// float2 g_PixelateParam = float2(BackBufSizeX / 8, BackBufSizeY / 8)
TexCoord = floor(TexCoord * g_PixelateParam) / g_PixelateParam;
float4 Color = tex2D(RenderTargetSampler, TexCoord);

Then for each pixel I calculate its luminance using weighted average of RGB values:

float Grayscale = dot(Color.rgb, float3(0.299, 0.587, 0.114));

And finally I'm doing a lookup into specially prepared volume texture. XY coordinates are taken from texel position in screen space, while Z (depth) coordinate is just the pixel luminance.

float2 TexXY = (Pos-float2(0.5,0.5))/g_VolumeLookupTextureSize.xy;
float  TexZ = Grayscale;
float4 VolSample = tex3D(VolumeLookupSampler, float3(TexXY.x, TexXY.y, TexZ));
Color.rgb = VolSample.rgb;

The texture is prepared so that its subsequent slices contain ASCII characters: from empty black image, through dark gray dot on black background, dark gray comma, colon, until white hash on light gray background and finally blank white image. Here you can download this texture (I've made it using GIMP and DirectX Texture Tool): Atari Font.dds.

To make it pixel-perfect, I had to bias XY texture coordinate by (-0.5, -0.5) texels, as well as turn off texture filtering:

Dev->SetSamplerState(3, D3DSAMP_MINFILTER, D3DTEXF_POINT);
Dev->SetSamplerState(3, D3DSAMP_MAGFILTER, D3DTEXF_POINT);

It also turned off smooth transitioning between slices in volume texture (it means ASCII characters are not blended together), It's what I actually wanted to do, but by the way I realized that we cannot switch filtering for separate texture coordinate axes (e.g. only UV or only W), just like we do with addressing modes (D3DSAMP_ADDRESSU and so on). It could be useful sometimes... Anyway, we can achieve that with pixel shader.

Comments | #rendering Share

Pages: 1 ... 63 64 65 66 67 ... 150