C64 Cool maze Generator (sort of)

As demonstrated by Casey Reas at the Eyeo Festival, June 2011, Minneapolis, Minnesota, a random maze generation program in one line of Commodore 64 Basic. The program uses the PETSCII character set, specifically the line character code of 205.5, plus a random occurrence of 1 or 0, which alternates between the / and \ characters, and then repeats without causing line breaks. This small program is shown running inside of the Vice emulator on Ubuntu. The recording was made with glc and compiz.

Point in Polygon.

Sometimes size coding is about small powerful snippets of code. Few better examples exist than this point in polygon code by Randolph Franklin.

Qoob added to GeeXLab

JeGX has added Qoob 1.0.2 support to his graphics quick prototyping tool GeeXLab.There is already a demo out. More about Qoob in GeeXLab and how to download.

Qoob added to ZGE

Vill Krumlinde has added Qoob 1.0.2 support to the ZGameEditor (ZGE). See the full details at the news section at the Qoob website as well as a link to the first ZGE demo containing qoob...

http://qoob.weebly.com/news.html

Qoob libs Released and Modeller Upgraded

Qoob libraries are out! You can now include qoob models in intros or anything really. To go with the libs, the modeller has been upgraded and many bugs removed. It should be 99% stable now. There are a few new features such as moving the model using the mouse (much requested). Oh and Undo now works ... ahem...better.

Check it out at http://qoob.weebly.com

Benoit Mandelbrot Dead

Rest in peace, sir.

Simple Code to Calculate normals for a Quad Mesh

I'm ripping iq here. However, I've fiound a lot of people haven't read his brilliant normals idea buried deep in one of his presentations, plus I add face normals and a subtle way to rewrite crossproduct that shortens code again.

Here is some tiny  pseudo-code to calculate both the vertex and face normals of a  mesh made of quads. It is pseudo-code because your mesh structure will not be the same as mine.  The idea is based on iqs idea in his Breakpoint presentation.

 for ( i=0; i<numberofquads; i++) {
         for (uint k=0; k<4; k++)  cross ( &quad[i].v[k], &quad[i].v[(k+1)&3], &facenormals[i] );
         for (uint k=0; k<4; k++)  add ( &facenormals[i], &vertexnormals[&quad[i].v[k]]);
 }

Now this neat and easy to read and incredibly small for such power. Essentially it is:

for each quad
    for each edge in quad
         accumulate crossproduct of edge vertices into face normal
   for each vertex in quad
         add face normal

One subtle trick here in the code is that cross product is redefined thus:
cross(v1,v2,v3) ::  v3 = v3 + crossproduct (v1,v2)
Add is as you expect::
add(v1,v2):: v2=v2+v1;

During qoob modeller writing I found redefining cross product in this way was fine, after all it can be called with a zeroed vector in last place if a true cross product is required rather than accumulating. If you don't understand how accumulating cross products of each edge of the polygon equates to calculating a normal, see iqs presentation. That is the really smart thing here.

N.B.: Assumes facenormals and vertexnormals contain zero values before calling this function.
 The normals are not normalised (leave that to shaders or GL_NORMALIZE).

Qoob moved to its own website

So that this blog can get back to non-qoob stuff, qoob has been moved to http://qoob.weebly.com
The whole package including .h and .o to link against will be out (this weekend) ermm not quite.. real soon now.

Qoob (OpenGL version) final results

Qoob library for 3d modelling and uncompression of 3d models is compiled in two ways. One includes all the loading and saving etc used for modelling. The other mode is an intro mode. After making a basic test intro with qoob, I discovered speed was a factor and had to rewrite a few routines. This forced me to add a few bytes but not too many. Now finding normals and smoothing are much much faster and models typically load in sub-second time.This is important if we are using 50+ models in an intro - compo rules usually enforce a total run time that includes loading/unpacking.

The final size using crinkler 1.1 with settings :
/CRINKLER /COMPMODE:SLOW  /ORDERTRIES:3000 /UNSAFEIMPORT /REPORT:report.html /TRANSFORM:CALLS
is 2165 bytes.

This includes, selection handling and recording specific polygons used in modelling, 3d maths lib, catmull clarke smoothing with holes, subdivision, insertion and deletion, unpack routine, extrusion, tapering, bulging, rotations, translations and scaling on polygons and model level, making a cage and making rounded holes, basic cube geometry, vertex and face normals.

Models vary in size. The largest I've done so far is around 350 bytes which was a unicorn head. The compression of models is better than I predicted as picking polygons early in modelling is inexpensive as polygon ids fit within one byte and crinkler does a good job with them. Most abstract models come in around 30-70 bytes and most real world ones 100-200. Better than expected.

If you want to play with the qoob modeller (opengl), send me an email on my gmail account chris thornborrow and I'll release it to you. Especially if you are a 3d modeller used to wings3d - I'd like feedback.

3d Modelling : the challenges for Compression

Quick reminder, qoob is a modeller and library that stores 3d models by a series of modelling commands, not by storing the mesh. The hope is to get smaller models for intros. As I write qoob, three fundamental challenges are emerging:

1. The size of the qoob library with the modelling commands code
2. Storing modelling commands in a compact way
3. Picking and selection compression

The Size of the Library
The Qoob library is around 2k after compression. It must be included in intros to decode cube models. As such the existing library simply wont work at 4k. Its fine for 64k and for 8k/16k. However I'm also hopeful a much smaller one could be produced. There would be three keys:

• use DX maths and subdivision
• reduce the modelling options and target abstract objects ONLY
• use default values for all functions so storing a model means storing only a series of commands - no parameters.

That may seem crazy but there are a huge range of abstract objects that can be done this way. From plants to cubes to geometric abstracts. Even basic human figures.The first characters I showed on this blog were done this way!

Storing Modelling Commands

I made the mistake of targetting a low number of entry points in qoob lib. This kept the library small and tight but meant even a simple extrude needed 9 bytes to store!! However after considerable redesign, I've managed to reduce the average byte count per modelling command to less than 2. The result is less compressible but not by much and a factor of 5x on average is a very good saving. 50 modelling commands is a enough for many models. Thats 100 bytes BEFORE compression.

The first trick was to increase the number of possible commands (eg translate became translate, translateX, translateY, translateZ). Translate in X requires only one float whereas translate requires 3. Often the modeller does not need the full expressive power. In most cases the reduced bytes needed to store the new commands parameters far outweigh the extra code, which is highly compressible.


The second trick comes from accepting that we dont need the full range and accuracy of floats. A single byte is enough for most functions and should greater range be required, the modeller can always concatenate. For example, a translate in X can be expressed as a single byte. If further translation is required, the modeller simply translates again, however usually this is not the case.


Selection Compression

A talk with iq depressed me. Essentially selections needs 5 bytes (command and quad id) to store. In addition polygon ids are random (over many picks) and so do not compress. Iq guessed that 50 picks would render qoob models less effective than mesh based compression.
Well this is a fundamental mathematical barrier. The trick is to avoid it. Procedural selection comes to the rescue. Commands like "select similar" from wings3d mean that the modeller picks a single seed polygon then expands the selection using a command or two.
I'm still exploring the solution here so more when I'm sure what is a good thing but Im pleased with what I have so far.

So qoob lib got bigger but that could be fixed by porting to dx and reducing flexibility. Models got much smaller and picking is nearly solved but again costs bytes in the library.

Simple Algebraic Surfaces Reference

Serious size coding involves trawling forums and the net for ideas and resources. Here is a little link that came over twitter this morning with a bunch of tiny algebraic surfaces that may, or may not, be useful:

http://www.freigeist.cc/gallery.html

Qoob Matures

Qoob now has about 80% of the functionality I want in a basic modeller, at least for now. For personal reasons I will take a break from coding for a few weeks and leave you with a few more sample images. The next step will be to make an actual intro using the tool.



Click on the images for larger versions. I've managed to get some organic, some holes and some asymmetry into the modeller. Undo is implemented (well,ok, one level). The next major step is to put the geometry lib into a 64k framework.





But a burning question is - how big is the Qoob library? Whats the overhead?
Here is a test I performed.
Using crinkler 1.0 ( I cant get 1.1 to work for me) I constructed a minimal OGL program : 600 bytes after compression. I then added Qoob library and called each function once to force inclusion. The program size was 2.4k with crinkler settings of /CRINKLER /COMPMODE:SLOW /ORDERTRIES:3000 /UNSAFEIMPORT. No smarts here to help crinkler and probably not the right settings. Likely, the library can shrink a bit but also could grow a little with the few functions I have left to put in. Its safe to assume therefore that <2k is the Qoob overhead.

2k - thats good, better than I expected. Very useful for 64k. The models range from 3 bytes (a chamfered cube) to 200 for the characters.

Maybe its worth rewriting this using DirectX and getting it into 4ks after all? The 4k might be non-demoscene standard - a sort of model show in 4k...but thats an achievement by itself in some ways.

Shorter code for Point in Interval

Nice little coding trick for checking if a value lies within two other values. The result is faster and (slightly) smaller than checking both values. The trick could be extended to do bounding box intersections for collision detection for example.

Neat trick

It resolves down to this macro:

#define InRange(ch, a, b) (unsigned((ch) - (a)) <= (b) - (a))

.cool

Qoob Character modelling

So, Qoob, the tiny modeller, finally is competent enough to model simple characters. Its all a bit pikachu for now - but that may be more my inner pokemon than the tool, not sure yet. The qoob library grew hardly at all to support this, only the modeller.

Characters are about 200 bytes. Thats ok but not great. The culprit is picking. You do quite a lot of polygon picking to model the limbs, eyes, nose etc. Click on the images to see larger versions.



Picking consists of a command (1 byte) and a polygon (3 bytes). Thats 4 bytes before compression. Assuming the command compresses well, the specific polygon id is the problem. A lot of the time the first byte will be zero which will help. Still, we can assume a total of 3 bytes on average per pick after compression. These models take about 50 picks. Hence 150 bytes as a base. Ideas:
1. Store the command pick n times, (meaning select the next polygon n away in the array). This means great compression but even so, thats a lot of data to compress and there may be problems.
2. Duplicate what the modeller does, by storing the 2d pick co-ordinates and have qoob lib project that into polygon space. Well its 2-3 bytes anyway and then the projection code. So no.
3. Delta encode the polygon id. In my modelling at least this would help often. Polygons being picked often come from the same base polygon in the model before subdivision and therefore their ids are similar.
4. Exploit hierarchy of subdivision more ... have to think here. In theory a polygon might be identified by 3 bits for original face of cube (the base input)2 bits x n where n is the subdivision level.
5. Restrict picking to be pick + grow pick. This would help with large groups of polys but the modeller would go nuts.

... hmm need to think more, none of the above convince me.

3d Modelling thoughts.

The objective of Qoob is to be a demoscene modeller that targets 64k intros. It should allow hundreds of models in a 64k. That means man made and organic. Organic seems to require arbitrary extrusion (think pipe or ribbon). It allows for models like loonies use in their 4ks eg benetoite and, more impressively, 64ks such as Flight666. The maths for modelling with arbitrary extrusions is quite large (>500 bytes) and adds a lot of bytes to Qoob which is already growing in size.

In addition, Qoob must support selecting individual polygons for arbitrary complex shapes. That will be the key to true modelling. But selecting, say 50 polygons currently requires:
select p1
select p2
select p3
... 50 selections
to be stored and compressed. Compressing the command is obvious and cool. I'll just store the command queue and the data queue seperately. The data for each entry is four bytes and may not compress well. I could try sorting and delta encoding - the usual tricks - of course. This worries me.

Size wise then, I'm struggling now: selections and extrusions add lots of bytes. ONe to the lib and one to the models. Suggestions are welcome.

However, on the bright side, Qoob could support displacements on large and small scale, like sculpting. I might therefore be able to create highly detailed geometry with bumps and ridges, for very little cost.

In the mean time, some screenies of what can be done without such functions:







p.s. Hope people like the new design for the pages here. Also check out the demotivation demoscene picture to the right (with apologies to iq/mentor) as elevated races toward 500 thumbs on Pouet.

Catmull Clark Subdivision Musings

Before you read on. Blogger is simply crap for posting code. I've done my best for formatting but if you see dodgy symbols or things that make no sense - blame blogger as this code is right out of the compiler.

Modellers seems to like quads. Catmull Clark subdivision smooths and maintains a quads only model. Doo-sabin introduces triangles. Loop works on triangles. So I decided to use Catmull clark in qoob. I got it working last night after spending a whole weekend when I should have been in the sun. The model above, I estimate, would be around 22 bytes to store compressed. Its approaching organic but is still embarressingly geometrical. Thats has to be the next goal, to produce some organic stuff.

Most code on the net works using winged edge data structures. Classes abound. The examples are no use for size coders. Fortunately iq tackled CCSD in his 2007 presentation for breakpoint, Tricks and techniques for RGBAs Past and Future Intros.

(By the way his normal a mesh trick in that presentation is without doubt the best piece of size coding I've seen.)

Firstly wikipedia has a description of the algorithm. Unfortunately, its not totally clear what an edge point is -the midpoint of an edge or the new displaced midpoint of the edge (its the first). But there are other references to clear this up. IQ proved its possible to do Catmull clark without winged edges but still he uses edge ids. I wanted to avoid this and did so but in doing so, each time I add a vertex I loop through all vertices to see if an identical one already exists. I think its a case of what I gain on the flat I lose on the hill. Here is the final code in old style C (ie no C++ operators for maths) which makes it look horrendous - thats why operators were introduced :-).

addVert is key. It checks all existing vertices for an exact duplicate (exact is fine in this case) and returns either the index to the existing one or adds the new vertex and returns its index. addquad adds a quad to the model. The last line deletes old quadsr. The routine supports subdivision without displacement and CCSD, hence the if(smooth) in places.

Vert disp[MAXSIZE]; // displacements
uint val[MAXSIZE];  // valences

void subdObj (Object *ob, uint smooth) {
Vert tmp,ep,fp;
uint eid[4],cni; //indices for new vertices, edges and centre
uint onq = ob->nq;
uint onv = ob->nv;

ZeroMemory(disp,MAXSIZE*sizeof(Vert));
ZeroMemory(val,MAXSIZE*sizeof(uint));
for (uint iq=0; iq < onq; iq++  ) {
          centroid (ob, iq, &fp);                        
          cni=addVert(ob,&fp);                       
          for (uint v=0; v<4; v++  ) { // for each vertex in each quad quad
              lerp(&(QV(ob,iq,v)), &(QV(ob,iq,(v 1)&3)), 0.5f, &ep);                                 
              copy(&ep,&tmp);                                  
              if (smooth) smul(&tmp,0.5f);                                 
              eid[v]=addVert(ob,&tmp);   // orignal vertices of edge/4.0                                 
              // add contrib of face points to displacement for new edge points                                 
              smadd (&fp,0.25f, &(disp[eid[v]]), &(disp[eid[v]]) ); // add fp/4 to edge vector                                 
              // add face points to displacement for original point
             add (&fp, &(disp[ob->q[iq][v]]),&(disp[ob->q[iq][v]]) );
             // add 2x edge points to disp for original points
             smadd (&ep, 2.0f, &(disp[ob->q[iq][v]]),&(disp[ob->q[iq][v]]) );
             val[ob->q[iq][v]]  ; // add up valences
       }
  // now construct four new quads
for (uint k=0;k<4;k++  ) addQuad (ob, ob->q[iq][k], eid[k], cni, eid[(k-1)&3], selected(iq));
}
// now displace all vertices...face points will be unaffected
if (smooth) for (uint v=0; v <q->nv; v++  ) {
  if (v < onv) { // this must be an original point     
     smul (&(disp[v]), 1.0f/val[v]);     // average the displacement values     
     smadd  (&(ob->v[v]), val[v]-3.0f, &(disp[v]), &(ob->v[v]) ); // correct for extraordinary vertex
     smul (&(ob->v[v]), 1.0f/val[v]);     // divide through by valence
  } else add (&(ob->v[v]), &(disp[v]), &(ob->v[v]));
}
for (uint iq=0; iq<onq; iq++  ) delQuad(ob,0);
}

Well depending how you count lines of code its 20-25. addVert and addQuad make it 25-30. So lets call it 30 lines of code Catmull Clark in C. C++ operators would make this a bit shorter. IQ claims 50 lines of code but if counted in the same way, his code is about the same 30-35.

The way the code works is a two pass algorithm first over quads of the original model and secondly over the vertices of the new model. The first pass subdivides and accumulates displacement in a seperate vector. This enables the first pass to calculate all the valences and store them before averaging the final displacement and applying it in the correct manner depending on the type of point (original, edge or face). There are a couple of gotchas but thats the basic idea. No winged edge, infact no edges at all.

Coding style sucks. Happy with result so thought I'd publish it.

One cool thing is the model pictures is about 22 bytes to store. A champfered cube is about 12 bytes and a sphere similar. It means we are looking at qoob providing a library of demo type objects in a few hundred bytes. The spheres are made of quads and do not suffer from peaks at top and bottom. Ther qoob library is a few kilo unfortunately. DX would help but I think I'll target 64k so not to worry.

Qoob Progressing

My modeller is progressing. Heres a screen shot:



The model in the picture takes about 30 bytes to store. Smoothing is next up.
Organic stuff is escaping me right now but I'll work on that.

stupid idea 247: worlds smallest vector maths library

Here is a tiny 3d vector maths library:

typedef float vec3[3];
vec3 *vec(vec3 *v, float x) {v[0]=v[1]=v[2]=x;return v;}
float *mav(vec3 *v1,vec3 *v2,vec3 *v3,vec3 *v4,vec3 *v5){
  for (int i=0; i!=3; i++) v3[i]=v1[i]*v4[i]+v2[i]*v5[i];
 return v3[0]+v3[1]+v3[2];
}
vec3 VZERO={0,0,0};  vec3 VONE={1,1,1}; vec3 VMONE={-1,-1,-1};

Thats it. It can do zero, set, add, sub, length2, dotprod, negate, lerp, centroid. e.g add is :
mav(&v1, &v2, &v3, &VONE, &VONE ); // v3=v2+v1

Lerp means that centroid (the centre vertex of a quad) can be found without a division by using two lerps. For a moment it seems cool until you realise the calls to it dont compress all that well.
The challenges remaining are xprod, normalise and max/min. then I have everything for handling my 3d modeller qoob.If I can make minor adjustments to get those, this might be worth persuing.

Very .cool

GLSL Minifier.

"GLSL Minifier is a tool to pack GLSL shader code. It generates a code as small as possible that is equivalent to the input code. The generated code is also designed to compress well. It has been optimized for use with Crinkler, but should perform well with any other compression tool. GLSL Minifier generates a C header file you can include from your code."

Very .cool

3d modelling for Intros ? qoob.

I'm investigating meshes for a while. First attempts with Pohar from Rebels resulted in some pretty detailed modelling for 4k. It was the usual way. Create a mesh in a modelling tool, compress it, load it, smooth it, just the same as iqs approaches to the problem. As dx provides smoothing (loop I think), this results in tiny code and models of 500bytes or more as seed meshes. One of the problems with this technique is the model is equally "smooth" all over at the end. Its hard to have smooth parts and rough parts. Iq overcomes this by coding displacements.

This image fo a dragon was done using this technique and the result (with crinkler, shader, mesh and mesh code) was just over 2k...

Theres a good read about meshes in intros at Pouet.

I once did a 1k with several curved "lathe" objects, but it was com dropping and thats unreliable. I haven't fixed that so no code on Pouet right now. Maybe i'll try again with crinkler at some point. Lathes seem to be an option for modelling at 1k/4k. In the code I developed for gcc the models were just 8 bytes each before compression. The code to create the objects was around 350 after compression and the objects are curved: there is non-linear interpolation between points in the model. Click on the image to see what I mean.
But Lathes are limited.

Another technique I looked into was intersections of regular primitives. This can often produce surprising results. The idea is simply to rotate/translate a single primitive. The two screenshots below illustrate some results. The first is a rotated cone, resulting in a star. The second is a very small routine (180 bytes after compression) to generate organic like structures. Again no randomness, just rotate, translate, rotate stuff.




You can see the last one live in the second half of the awesomely coloured :-) 4k intro Fruit of the Loop.

But my goal is always to get away from embarressingly geometrical to something that looks modelled. It occurred to me that crinkler is very successful because it works at compile stage for compression, its not simply an exe packer. Thus my latest project is a modeller, the idea being to use the modelling commands to better compress the end model. qoob is a simple subdivision modeller based on wings3d functionality but very cut down. Its a fresh project but already I can see that no way will this be useful for 4k, only 64k. Thats disappointing but it comes from the fact that the library used to reproduce objects is 2-3k. An early screenshot is not impressive:


The idea remains right though: this is the modelling equivalent of a texture builder.