Category Archives: Coding - Page 2

From Vertex Positions to Packed Element Arrays

At my new workplace at university I'm currently porting an advanced terrain rendering engine from DirectX to OpenGL.
One of the performance optimizations the engine uses is that it draws the terrain tiles right from the index buffer without using a vertex buffer at all - that is it packs the vertex position into the 32-bit index and unpacks it in the vertex shader.

Why is this faster than rendering using a vertex buffer and no index buffer?

When using an index buffer the graphics card can make use of a cache of already transformed (vertex-shaded) vertices and when an index is reused, it can use the cached result instead of running the vertex shader again. Of course, this only works if there exists a certain temporal locality, but that is given.
If no index buffer is used, the vertex cache won't be used, because the implicit index is different for each vertex.

Since I need to port the engine from DirectX to OpenGL, I did some research to see if it is possible to do the same in OpenGL.
It's not really possible but you can achieve something quite similar in OpenGL 3.0.

Using the Input-Assembler Stage without Buffers (OpenGL)

This is meant as OpenGL analogon for Using the Input-Assembler Stage without Buffers (Direct3D 10).

I think the title is self-explanatory but for greater clarity let me rephrase it:
The aim is to render something without using vertex or index buffers, that is (in OpenGL speak) using neither vertex data nor an elements array to render something.
Instead the automatically supplied gl_VertexID attribute  (vertexId in DirectX) is used to determine the vertex the shader is currently processing.

The example in MSDN simply draws a triangle using vertexId:

VSOut VSmain(VSIn input)
{
VSOut output;

if (input.vertexId == 0)
output.pos = float4(0.0, 0.5, 0.5, 1.0);
else if (input.vertexId == 2)
output.pos = float4(0.5, -0.5, 0.5, 1.0);
else if (input.vertexId == 1)
output.pos = float4(-0.5, -0.5, 0.5, 1.0);

output.color = clamp(output.pos, 0, 1);

return output;
}

If you want to do the same thing in OpenGL, you have at least two problems:

  • OpenGL uses glVertex* as end marker for the specification of a single vertex and the array rendering commands (glDrawArrays, glDrawElements, etc.) all require an enabled vertex array.
  • gl_VertexID is only supplied if:
    • the vertex comes from a vertex array command that specifies a complete primitive (e.g. DrawArrays, DrawElements)
    • all enabled vertex arrays have non-zero buffer object bindings, and
    • the vertex does not come from a display list, even if the display list was compiled using DrawArrays / DrawElements with data sourced from buffer objects.

    (from GL_EXT_gpu_shader_4)

There is no way around these requirements, but what you can do is to create dummy vertex buffer with one element, bind it as vertex array and simply draw as many vertices as you want. If you don't access gl_Vertex there is no way that uninitialized data can affect the shader and although behavior is generally undefined in OpenGL, if you render beyond the vertex buffer size, it has worked so far that I've test this on.

Drawing a circle without accessing gl_Vertex

Drawing a circle without accessing gl_Vertex

You can download the source code here.

Packing Vertex Positions into the Elements Array

The next step is to start packing and unpacking data in the gl_VertexID. For this an integer type and bit operations (shifting and masking at least) are required in the vertex shader, so it requires GLSL 1.30 at least.

The code is quite short from my proof of concept project, so I'm pasting the shader here:

#version 130
#extension GL_EXT_gpu_shader4 : enable

out vec4 color;

vec3 unpackVertex(int index) {
return vec3( index & 0xFF, (index >> 8 ) & 0xFF, (index >> 16) & 0xFF ) * (2 / 255.0) - vec3(1.0);
}

void main()
{
vec3 unpackedData = unpackVertex( gl_VertexID );
gl_Position = vec4( unpackedData, 1.0 );
color = vec4( (unpackedData + 1.0) / 2.0, 1.0 );
}

In main.cpp the equivalent can be found for setting up the elements array:

#define packFloat(v)	(int(((v) + 1.0) / 2 * 255) & 255)
#define packVertex(x,y,z) (packFloat( x ) + (packFloat( y ) << 8 ) + (packFloat( z ) << 16))

void display(void) {
[...]

unsigned indices[] = {
packVertex( 0.0, 0.0, -1.0 ), packVertex( 1.0, 0.0, -1.0 ), packVertex( 1.0, 1.0, -1.0 ),
packVertex( 0.0, 0.0, -1.0 ), packVertex( -1.0, 0.0, -1.0 ), packVertex( -1.0, -1.0, -1.0 )
};
glDrawElements( GL_TRIANGLES, sizeof( indices ) / sizeof( *indices ), GL_UNSIGNED_INT, indices );

[...]
}

For the code to actually make sense I should initialize an index buffer/elements array buffer in OpenGL and upload the indices into it but this was just for testing.

Drawing two triangles by packing their position into the index buffer

Drawing two triangles by packing their position into the index buffer

You can download the source code here.

Note:
It has been brought to my attention (thanks Yagero), that on NVIDIA cards the driver currently reduces the element array data size from int to short, which causes the third byte (ie z values in this packing scheme) to always be 0.

A fix is to use an element array buffer (index buffer) which prevents the driver from messing with the data size.
You can download the adapted source code here. To show that it works, I have swapped the x and z component in the packing scheme.

Extending Java and Javac

Today I want to write about something I've been working ages ago - specifically in March I wanted to see if I can extend a Java compiler to support LINQ´ expressions, too.

I probably spend more time on finding a good open-source compiler to experiment with than I later spent on trying things out, so let me share my preferred source with you: http://openjdk.java.net/ is a good address to start with.
More specifically http://openjdk.java.net/groups/compiler/ contains some valuable information about the way the compiler works.
A nice thing is that there is a branch that has added support for ANTLR which makes added language a tad bit easier since you get to change a grammar file instead of tweaking hand-written lexers and parsers. More info about it can be found at http://openjdk.java.net/projects/compiler-grammar/.
You can download the source code from http://hg.openjdk.java.net/ - don't follow the link to http://hg.openjdk.java.net/compiler-grammar/compiler-grammar, that one will only allow you to download part of the branch´.

I didn't come around to add support for LINQ in the end, but to get known to the compiler and the ANTLR grammer, I added support for the var keyword as known from C#, which allows for automatic type deduction and for anonymous objects (again using the C# syntax). Thus my changes allowed for the following to compile and execute correctly:

public class Test {
	public  static void main(String[] args) {
		// automatic type deduction
		var t = Math.atan(1);
		System.out.println( t );

		// anonymous type
		var i = new { Amount = 108, message = "hello" };
		System.out.println( i.Amount );
	}
}

Read more »

PowerPoint Tools

I've finally managed to upload a version of my PowerPoint LaTeX add-in for PowerPoint 2007.

I'm just going to post a short Vimeo video here that shows how inline formulas work (the main feature):

I've tried to work on the add-in during my spring vacation but somehow I have instead spent all my time watching four seasons of House M.D. (which was totally worth it though :-) ).

There are still some features like support for MikeTeX, code clean-ups, small bugfixes and a preference window that I should work on, but I don't plan on selling it, so I don't really care if it's still somewhat work in progress.
I'm going to continue working on it when I have to use PowerPoint again.

You can check it out (and another add-in dubbed Language Painter that I wrote to fix some annoyances when writing presentations in languages different from your keyboard layout) at http://code.google.com/p/powerpointtools/.


Read more »

What I (don't) like about C#

I've been using C# personally quite a bit lately and want to share with you a list of the things I like or don't about it.

First the things I like about it (compared to C++ and Java sometimes):

  • The out and ref keywords are awesome
    You actually need to use them both when declaring out and reference parameters and in the actual function calls.
    This really avoids confusion and makes the code clearer compared to the way references are transparently handled in C++.
  • a class's definition and declaration is kept in just one file
    Avid C++ coders will probably disagree with me here, but I really like this way of coding things. It allows me to code faster and also reduces one source of compiler errors. To be honest I would probably go insane when coding in C++ if it wasn't for Visual Assist's nifty "Move Implementation to Source File" and "Create Declaration/Implementation" refactorings.
    Likewise one could say that C#'s (or .NET's) notion of assemblies is better and less messy than C/C++'s compilation units.
  • Properties are simply awesome
    Properties look like normal member variables but you can write your own getter and setter functions and also give both different access levels, so e.g. you can have a property that is public for reading but protected for writing.
    Moreover, you can have C# create the code automatically, so you just end up with a way to specify separate access levels.
  • Read-only variables can be set anywhere in the constructor
    If you know C++'s initialization lists, you will thank god for this feature, because this feature gives you a lot more freedom and again results in more readable code (at least in my opinion).
  • The override and new keywords are really handy
    Again this is a feature to avoid unnecessary bugs because you get warnings as soon as you "override" a method that doesn't exist.

What I don't like:

  • No typedefs
    This really bugs me, because the concept of typedefs is a good way to add abstraction to your code and the using keyword in C# only marginally improves the situation, because it only affects the current module.
  • No default/optional parameters
    You have to overload methods instead, which is kind of annoying. I hope this gets fixed sooner or later.
  • No inner classes like in Java
    Passing on references to constructors is annoying and inner classes in Java really help it quite often.
  • No synchronized keyword like in Java
    Again this is a nice-to-have feature because it would  clean up some code.

How to make WordPress display Full Text in RSS Feeds

... and why WordPress Moderators are obviously idiots

Today I got an email asking me to enable full text RSS feeds - so far so good, only when I activated the "Full Text" option nothing changed - neither in FireFox, nor in Google Reader, nor anywhere else. Only in Feed Proxy I saw a <content:encoded> tag appear that contained the full text (including html tags), but the description still only contained the excerpt (without html tags).

Before I link you to the thread that made me conclude the statement in the post title, let me quote from the RSS 2.0 specs:

A channel may contain any number of <item>s. An item may represent a "story" -- much like a story in a newspaper or magazine; if so its description is a synopsis of the story, and the link points to the full story. An item may also be complete in itself, if so, the description contains the text (entity-encoded HTML is allowed; see examples), and the link and title may be omitted. All elements of an item are optional, however at least one of title or description must be present.

That said take a look at http://wordpress.org/support/topic/190901 - having the problem described above and reading the replies, it just left me with one question:

If Otto42 is a moderator, where does WordPress get its trolls from?

The RSS Specs are pretty unspecific and blurry when it comes to the issue, one can at most point to http://www.feedvalidator.org/docs/warning/DuplicateDescriptionSemantics.html, but the main issue I have is that the rants of this "moderator" don't help me fix my problem, because Google Reader and FireFox still don't display the full entries.

A fix for it

If you want to fix it, you can do the following (in WP 2.7):

Open up wp-includes/feed-rss2.php and change

<?php if (get_option('rss_use_excerpt')) : ?>
<description><![CDATA[<?php the_excerpt_rss() ?>]]></description>
<?php else : ?>
<description><![CDATA[<?php the_excerpt_rss() ?>]]></description>
<?php if ( strlen( $post->post_content ) > 0 ) : ?>
<content:encoded><![CDATA[<?php the_content() ?>]]></content:encoded>
<?php else : ?>
<content:encoded><![CDATA[<?php the_excerpt_rss() ?>]]></content:encoded>
<?php endif; ?>
<?php endif; ?>

to

<?php if (get_option('rss_use_excerpt')) : ?>
<description><![CDATA[<?php the_excerpt_rss() ?>]]></description>
<?php else : ?>
<description><![CDATA[<?php the_content() ?>]]></description>
<?php endif; ?>

Similarly, if you want to fix your comments, too, open wp-includes/feed-rss2-comments.php and change

<?php if ( post_password_required($comment_post) ) : ?>
<description><?php echo ent2ncr(__('Protected Comments: Please enter your password to view comments.')); ?></description>
<content:encoded><![CDATA[<?php echo get_the_password_form() ?>]]></content:encoded>
<?php else : // post pass ?>
<description><?php comment_text_rss() ?></description>
<content:encoded><![CDATA[<?php comment_text() ?>]]></content:encoded>
<?php endif; // post pass

to

<?php if ( post_password_required($comment_post) ) : ?>
<description><![CDATA[<?php echo get_the_password_form() ?>]]></description>
<?php else : // post pass ?>
<description><![CDATA[<?php comment_text() ?>]]></description>
<?php endif; // post pass

Cheers,
Andreas

Seminar about Motion Retargeting

creatureanimationwbTwo weeks ago I had to give a presentation about Motion Retargeting, which I want to share with you now.
I created it due to me attending a seminar about the latest developments in Computer Graphics at university and my presentation was about the Siggraph '08 paper "Real-time Motion Retargeting to Highly Varied User-Created Morphologies" from Chris Hecker et al.
You can check it out on Chris Hecker's homepage - his website also contains a bunch of other really cool articles and presentations from various conferences, so it certainly is worth taking a look at it.

I've also sifted through quite a lot of IK papers and lectures for my presentation to understand the later part about the IK solver in Spore and I've found a few links that are a nice read:

Ive created a huge PowerPoint presentation for my seminar  :-) It includes a few videos (thanks again to Chris Hecker for uploading them and replying to my emails incredibly fast ´) and two awesome IK solvers that I've implemented with VBA macros´ to show how CCD and Particle IK solvers work.

You can find a zip with all the videos and high resolution images here (includes both a PPT 2003 file and a 2007 file). I've also uploaded a small version without videos, macros as PPT 2003 file here, if you don't feel like downloading the 23 MB .zip file.

Here's a YouTube video of the two IK solvers:

I've exported the code into an additional IK Playground presentation which contains just one slide and the two IK solvers with the setup you see in the video above. You can find the PPT 2003 version of it here and the 2007 one here.

I've zipped up the macros here if you want to use them in your own slides. I've also written a handy VBA form that allows one to edit everything more easily (the macros are hardly documented though, but if anyone really wants to use them and runs into problems - you can always drop me a line or two in a comment :) )

The IK Solver Tool Form

The IK Solver Tool Form

BTW I'm not sure you know about it´, but Blender contains an awesome video editor - the UI needs some time to get used to, but the online documentation has improved a lot and with it, it works like a charm. Blender also supports some pretty professional filters, so it's going to be my video editing tool of choice from now on.

Cheers,
Andreas

VGA Project for Technical Computer Science

Today I'm going to write´ about a project that I've worked on for university together with other students for technical computer science.

Some Introductory Words

Some background information first maybe: everybody has to participate in a small project for technical computer science during the course of their studies at my university. Usually it's just a small project done by a team of three students.
I was lucky though and had good marks in the final exams TCS in the first term and was offered with maybe 50 other students to participate in bigger projects that actually work with hardware and have bigger team sizes too (about 10 people usually).

The project started in my second term and due to us being quite lazy students and being not pressured from the faculty itself, only started really working on the project in our summer vacation which explains why we only finished it two weeks ago (mid/end of the third term).

The aim of the project was roughly to display stuff on a monitor by programming an AVR microcontroller as well as an FPGA . We further had a working networking interface (using an old 10 MBit Ethernet card) to retrieve the stuff we should display.
We had to write everything (from the Clients to access/connect to our hardware to the VGA signal output code) on our own (except for a uip network stack to use on the AVR microcontroller).

The hardware (which we didn't have to put together´) looks like this:

We actually started working on and off during the second term, but getting everything setup and running (the FPGA people could probably fill books with horrible stories about Xilinx...) took quite some time and we were incredibly happy when we could connect via network to the AVR for first time and make the little LEDs on the FPGA flash in a pattern.

More than half a year later we were quite happy to produce images like these on the screen though:

The Features

As you can read above the whole project didn't really have a specific outline, it was more like throwing hardware at us and telling us to get creative (and get something done, too, obviously :-) ).

We settled on some features when we really started to implement things and had a better intuition about what is possible and what we cannot do:

  • Java Client to communicate with the hardware
  • AVR server code only to communicate with the client and network card and transmit/pass through data to the FPGA
  • FPGA displays the data on the screen (as 80x40 ASCII output on a resolution of 640x480 at 60 Hz)
  • Fixed color and font tables (ASCII charset and the usual DOS terminal colors)
  • Custom font and color tables can be sent, too
  • AVR has a built-in web interface and can be accessed like a website and offers a small Web Client to send and display text messages on the screen (using the default colors and the usual ASCII charset)
  • Java Client has editors for all three content types (font, color, screen) and can show a preview
  • Java Client has an Image Converter that can take arbitrary images and create custom font, color and screen data to show them in the best way possible
  • AVR can also output log/debug messages as html in the web interface´. Click here and here or here for examples :-)

Moreover there is some unfinished stuff like a hardware emulator to test the Java client with (that was never properly finished) or a batch testsuite to send messages without having to use the Java Client´ or the prototype Java Client and the first version of it (different codebase from what I've heard) etc. etc.

You can download the code for the AVR and its subprojects (testsuite, emulator) here.

The Final "Product"

First, let's take a look at what you see after you power everything up:

ETI is the abbreviation for Introduction to Technical Computer Science and GP4 stands for our project (including its number).

Next we have photo of the old terminal we were using to display debug information from the AVR (I spent hours reading it while coding the AVR):

Let's take a look at the web client now:

The Web ClientThe Java Client is more awesome though.

I'll just drop a few pictures showing and the results on the real screen:

For the rest I've prepared a litttle slideshow:

The Development

We were a team of ten students, which is quite huge (at least for my taste - and it also turned out to be quite difficult to manage). Three of us volunteered to be the official project leads, ie. the people responsible for keeping an eye on everything, organizing meetings and being the contact persons for Dr. Acher from the TCS chair.

We initially divided us up into 3 teams: an FPGA team, an AVR team and a Java Client team. The Java Client team and the FPGA one were the biggest ones, because we thought most of the work had to be done there (that turned out to be true), while the AVR team only consisted of me (doing all the C programming for the project) and Andreas Hubel who wrote the HTML/JavaScript code for the web client amongst other things. In retrospect the AVR was a lot of work, too, and, of course, underestimated by me, because I thought passing along information from A (the Java Client) to B (the FPGA) could be done in a day, which was not true.

A big chunk of the project was done in 3 days during our summer vacation when we all met and locked ourselves up in the lab and worked on the project from 9 am to 9 pm´. The rest was coded during various afternoons and sometimes weekends in our third term.

Read more »

Learn Java Interfaces in 10 Minutes

I've written a small Eclipse project´ that tries to explain interfaces and their use through commented code examples. It also shows how to make for-each loops support iterating over your classes and how to use the iterator interface to create data to iterate over just in time.

You can find the project here.

Cheers,
Andreas

WordPress Hacking II

privatepagesfixI have a few private pages that I use to store random stuff and ideas and private pages (for a reason I don't understand) don't show up in the pages widget.

It turns out that WordPress's get_pages function always filters them out, while get_posts doesn't (it actually has some logic to figure out whether to show private pages or not).

I've decided to fix this. A real fix would probably be merging get_pages and get_posts because both seem to do pretty much the same except that get_posts is a tad bit more advanced, but I'm all for quick fixes at the moment, because I don't have much time and I don't want to end up considering myself a PHP developer ;-)

To make get_pages return private pages, too, you have to open the file wp-includes/post.php and change the following lines near the bottom of the get_pages function:

	$query = "SELECT * FROM $wpdb->posts $join WHERE (post_type = 'page' AND post_status = 'publish') $where ";
	$query .= $author_query;
	$query .= " ORDER BY " . $sort_column . " " . $sort_order ;

to:

	$private_pages_inclusion_where = "";
	if ( is_user_logged_in() ) {
		$private_pages_inclusion_where  = current_user_can( "read_private_pages" ) ? " OR post_status = 'private'" : " OR post_author = $user_ID AND post_status = 'private'";
	}

	$query = "SELECT * FROM $wpdb->posts $join WHERE (post_type = 'page' AND (post_status = 'publish' $private_pages_inclusion_where)) $where ";
	$query .= $author_query;
	$query .= " ORDER BY " . $sort_column . " " . $sort_order ;

If you also want to make it easier to distinguish private pages from normal ones, you can also change the following bits in wp-includes/classes.php in the method Walker_Page::start_el:

$output .= $indent . '<li class="' . $css_class . '"><a href="' . get_page_link($page->ID) .
	'" title="' . attribute_escape(apply_filters('the_title', $page->post_title)) . '">' .
	$link_before . apply_filters('the_title', $page->post_title) . $link_after . '</a>';

to:

$output .= $indent . '<li class="' . $css_class . '"><a href="' . get_page_link($page->ID) .
	'" title="' . attribute_escape(apply_filters('the_title', $page->post_title)) . '">' .
	$link_before . apply_filters('the_title', $page->post_title) . ($page->post_status == 'private' ? " (Private)" : "") . $link_after . '</a>';

Cheers,
Andreas

Best-of-Explosm Web 2.0

Yahoo Pipes are an interesting concept, as are the other existing mashup tools (like Microsoft's Popfly or Ubiquity), and it is amazing what can be done with a few clicks with them.

Because I've wanted to learn how to work with Yahoo Pipes (before the Google Mashup Editor is released to the public), I've decided to take my best-of-explosm viewer to a different level and prototype it with Yahoo Pipes.

This just shows the first page (it's easier to view - and create - the feed in groups of 20 pictures than all at once). You can follow the link if you want to view more pages.

Stay tuned for more.
Cheers,
Andreas