Dark Bit Factory & Gravity
GENERAL => Projects => Topic started by: taj on November 03, 2006
-
Hi folks,
OK here is my latest work in progress (WIP). Its a wip, not a release.
Its <1k at the moment and I think is a very nice model for 1k. Its a surface with 5 candlesticks and a goblet.
It uses some nasty techniques so may not run everywhere so there is an image too. Even I am amazed this fits into 1k:
and I still have 25 bytes left maybe for one more model or an effect.
Not much to say else. Let me know if you have any ideas how to improve it.
-
Runs fine on my machine (1ghz Athlon, FX5900XT nVidia).
Looks really good, its amazing what can be done with such small space. Heck the picture is more than 26 times the size.
-
Thanks for the comment cirux. Glad it works on nvidia too!
Well I forgot its Friday and everyone has lives to go to :-) so I went ahead and released a version of this at intro inferno anyway.
Its different to the one here.
http://www.intro-inferno.com/production.php?id=1611
-
Works fine here, very impressive stuff in 1Kb O0
Both versions are really cool!
-
Thanks for the vote at II Rbraz :cheers:. I know you really know what it means to make a 1k so I'm pleased you liked it. I must admit I had to drop into a few lines of asm to get this one into 1k : C just couldnt do it this time. I used to be a C only man but there are tmies you just have to go to asm in 1k.
-
It should be well over Pouet too, I'm sure :)
About C x ASM, I will only work with ASM for now, some things I can't make tiny enough in C than ASM, like the attached "1k graveyard" that I was planning to release for CC compo, I did it using FASM.
-
Rbraz...aha now I see where the 4k came from :-). Did you try it in C first or just assume it couldnt be done and go straight to ASM?
-
I did it first in C and the best size was 1168 bytes , so, I recoded it in ASM and the final size was 1002 bytes , probably I'm not a good C tiny coder :P
-
1168 to 1002? Without ordinal imports I guess right(the C)?
Thats the first real number I've heard showing the difference between C and asm. Given about 450 bytes is the windowing stuff and cant be compressed down in asm, that means you were about 30% more efficient in asm!! I guessed it was more like 10-15%. Hmmm.
-
The worst part is that I have used ordinal import for both versions :(
-
At some point Taj, it would be really very cool if you could do a tutorial of how the maths works for this, and then how to go from there to the asm, and the asm to this miniscule exe. The thought process is as interesting as the code and end result - to me anyway :)
Jim
-
Well I wouldnt worry, religious bigots object to IBO but the rest of us know that if its used with opengl, it works 95% of the time - more than shaders, OGL extensions or anything written with the latest DX libs.
-
@JIM : gladly Jim, but remember I use only tiny amounts of asm (in this there are 3 lines of asm) so it really would be thought process not anything about asm. Everything is in C. So the tutorial would be something like:
1. Three steps to make your first tiny C executable
2. Making an opengl window tiny
3. How to do curved surfaces in a tiny way
4. Some big cheats to use
If thats still of interest, I can do it in a few parts over time.
I'd leave any and all asm parts of the tutorial to rbraz as I know very little about the subject (just enough to cheat).
-
Looks really impressive from the Screenie. I will have to download this when I get home to a decent pc, welldone Taj dude:)
-
Works perfectly here ... great work as always, taj !
-
i love it!
-
Absolutely fab :)
Nice one mate!
-
Hey I did it just so you could download a demo over a 56k modem ;-) good to see you back(wards).
-
good to see you back(wards).
Yay! You got my joke, and spookily you are right, your 1kb was the only thing I downloaded on my 56kb modem :)
Back on BB again now thank goodness.
-
At some point Taj, it would be really very cool if you could do a tutorial of how the maths works for this, and then how to go from there to the asm, and the asm to this miniscule exe. The thought process is as interesting as the code and end result - to me anyway :)
Jim
OK you asked for it.
Brain Dump - how to get curved surfaces in 1k
OK first off, a little 1k background. A windows 1k can be split into 450 bytes for windowing, a counter, swapping buffers etc. This leaves less than 500 bytes to do the dirty work. So we are looking for a routine around 350 bytes, plus a few models, plus an effect, plus colours and lighting. Ye gods.
So what can we dismiss quickly? NURBS wont fit, too much data. Subdivision surfaces are too big code. OK so standard stuff wont work. We could fall back to doing something abstract from Paul Bourkes web pages (again) or maybe this : http://mathworld.wolfram.com/SurfaceofRevolution.html. Surfaces of revolution. These are simple and work by defining a curve in 2d and the rotating this around an axis to get 3d. Hence the name. So we have a viable technique for producing complex curved surfaces in 3d in 1k.
However what I wanted to do was a specific object, not an abstract shape. It turns out surfaces of revolution can do this. If we define a set of specific points rather than a curve in 2d, we can rotate these around the axis and join them up into a mesh of triangles. See image 1 below. So we define 6 points and we have the outline of a pillar. Its not curved yet, its just a set of points of course.
To rotate around the y axis, we can use sin and cos. The x position of the point is the radius of rotation. So now to get nice smooth surfaces around the object (in this case a pillar from a church) we simply use very small angles (say 5 degrees) and step each point in the object around a circle. That simple! We then join these points into triangles. This is cool because a single assembly command fsincos can return the sin and cosine of the angle so we know this code will be very small.
But wait we now have a problem. We know we can do smooth surfaces around the object but what about up and down it. Surely just joinging the points will result in straight edges up and down. What we really want is more like image2 below whnere the outline of the object (the pillar) is curved too.
So lets consider some options:
1. We could define a lot of points (PRO, easy to do, no more code, CON large amount of data, only one object maximum possible)
2. Use a curved interpolator between the points like bezier or spline in 2d. (PRO, known to work, CON Too much code)
3. Use a simpler curved interpolator.
Here is a very simple curved interpolator and an explanation of how to interpolate a set of points into a curve:
http://local.wasp.uwa.edu.au/~pbourke/other/interpolation/
Notice the cosine interpolator. We may be able to fit this into 1k as cos can be a single instruction of assembler in our code. So now we have a scheme for stepping slowly along *between* the points in small incremental steps using an interpolator. This means we can now go up and around the object in smooth curves! We are almost there.
OK but I'm still not ready to start as I dont know how to store objects yet. Image 3 below shows a normal/typical way. Each point would be stored as an (x,y) pair. Hmm but each float is 4 bytes so the goblet would be 14 (points) x 2 (x,y) x 4 bytes. = 112 bytes. No it wont compress well as each point is quite different. Integers too are 4 bytes, though they will compress better (reasons are complex so I wont detail here). But still 100 bytes give or take is too much when our total budget for code and everything is <500!
So lets get smart:
1. Lets limit the range of values to say 1..16. Thats 4 bits per co-ordinate.
2. Lets store x,y in the same byte. Thats an entire 2d vertex in 1 byte.
3. Lets use 1 byte to store the numbr of vertices in the outline (4 bits = up to 16 vertices) and also store how to draw it (lines, triangles, quads etc, another 4 bits).
This will complicate code a little but its basically & and >> to extract the x,y from a single byte and those functions are very very cheap.
So now the goblet fits into 15 bytes! The pillar in 7. We are in business.
OK you have a working theory so now you write the code. This is what happens: its way too big. Normally its around 1200-1300 bytes. This is depressing and scary the first time. So now you need to know how to get things smaller.
Rule 1: Do not use math library, use your own (asm) math functions. Here are some useful ones for GCC:
asm ("fsin" : "=t" (a): "0" (a)); // not a=sin(a);
asm ("fcos" : "=t" (a): "0" (a)); // not a=cos(a);
asm ("fsincos" : "=t" (newct), "=u" (newst) : "0" (t)); // not newct=cos(t); newst=sin(t);
Yes thats real GCC C code above. It will save loads of bytes. You save pulling in the maths lib (thats 20+ bytes saved) you save the first function call into maths lib (that could be 14 bytes per function (ie 14 for cos, 14 for sin)) and you save the second fucntion call which is going to be maybe 6 bytes in this case after compression. It doesnt sound a lot but believe me it all helps.
I discovered the cosine interpolator was too much floating point maths. So I got clever and defined a very very simple curved interpolator. I'm sorry but I think its my major advantage here so I'm not going to reveal it. However the point is when you get stuck, understand the basics of the algorith and ditch what you really dont need. In my case Do I really need the curves to be continuous through points or do I just want curves between any two points? OK then well given two points any curve between them will do.
Some things I discovered. We can go up and around the object smoothly in as many steps as we like. Lets call the up value t and the around value s. This is great because now to get texture co-ordinates on the object we simply call glTexture2f(s,t); One line of code to generate our texture co-ordinates. Alternatively you can use s and t in some creative way to define colour (glColour3f(s,t,s+t); ) at each vertex. Normals were tricky. I discovered one last trick.
Using s,t as input to our up and around co-ordinate generators, we get back a a point in space (x,y,z). In my case these are in the range (-1.0..1.0, 0..1.0,-1.0..1.0). So lets do this: glNormal3f (x,2*y-1,z); What would the normals look like? Anyone? No? Anyone? No? Anyone? They would be spherical normals. This means *any* object we define would be lit as if it was a sphere(*). Guess what? You cant tell. The eye is completely fooled (if you dont add specular light). It is quite impossible to tell and is very cheap.
(*) this was misleading as Jim pointed out, the lighting on the object is calculated in the same way it would be for a sphere is a better way to say it...
Result. We have curved objects, texture co-ordinates and fake normals for very very little code.
In the end I plumped for more objects and dumped the texture and lighting. Mainly this was because setting up good textures and lighting was too expensive. Nontheless you can see how sometimes with some creativity, cutting corners etc. things get really really small.
I will provide source code for this article to members who request it- with no warranty at all. Its a mess but the two routines I use to generate the objects are pretty clear when read with this article.
Thats it for now, maybe this should be moved to the general discussion section?
Anyway I hope you have at least gained some insight into how hard it is to do a decent 1k intro. Its not a matter of just reducing code size but also of finding 2-3 tricks for making algorithms smaller and also knowing where to start. Data types and stored data must be reduced to the minimum and this requires creativity and an understanding of how data types are stored/converted and how they convert.
The same is true of 4k of course.
-
Some good information there.
-
Thanks Taj!
I like the term Brain Dump :)
So obviously you don't bother to store the object anywhere, you just hammer out the triangles when you generate them, and you don't worry about not re-generating the same points over and over again (to go round and draw at the same time) and you don't worry about linking the triangles at the other end of the circle. Of course you don't, because you don't need to :)
Your normals aren't quite on a sphere, but they're damned close, more like an object with 2 circular based cones stuck together on their bases, but who cares because it doesn't matter!
And for your rotating plate with the shrinking/growing vases you just vary the range of s or t to make more or less of the object.
When you make the exe, do you use special options for gcc and a special packer afterwards? Or can ld really produce such tiny (and non-standard!) PE files directly?
We used to have a kind of bezier interpolation we used in some of our games which was something like
-a + 9b + 9c -d
where a,b,c,d would be neighbouring points (heights on a height map). The big advantage of using those weights instead of normal bezier ones is
a x 9 = lea eax,[eax+eax*8]
and
-1 + 9 + 9 -1 = 16
so when you divide by 16 to do your final scale it's just
shr eax,4
That made it really fast and really tiny.
Anyway, rambling. Karma.
Jim
-
So obviously you don't bother to store the object anywhere, you just hammer out the triangles when you generate them, and you don't worry about not re-generating the same points over and over again (to go round and draw at the same time) and you don't worry about linking the triangles at the other end of the circle. Of course you don't, because you don't need to :)
Correct, correct and correct :-)
I dont use display lists as its 3 more OGl calls which is too much for me. So yes thats right I dont store the objects but regenerate each iteration. It limits me on how curvy the objects can be (too many points to calculate). In the 4k version, I "wasted" the bytes to create display lists. No I dont worry about joining the end points as they will have the same normal. Again its a performance thing only and in 1k we cant care too much.
Your normals aren't quite on a sphere, but they're damned close, more like an object with 2 circular based cones stuck together on their bases, but who cares because it doesn't matter!
No, they really are on a sphere. Maybe its definition. The normal at any point on a sphere centered at (0,0,0) as you know is just the point itself.
So I centered the object at 0,0,0 (with the y*2-1) and then used the point for the normal. It really is using spherical normals.
And for your rotating plate with the shrinking/growing vases you just vary the range of s or t to make more or less of the object.
lol they are meant to be candlesticks not vases - my wife complained they didnt look like candlesticks either :-). I guess have only 16 co-ordinates is a bit too much of a compromise.
When you make the exe, do you use special options for gcc and a special packer afterwards? Or can ld really produce such tiny (and non-standard!) PE files directly?
It goes...compile the C-> convert to a .com -> compress. It uses the framework from auld
http://in4k.untergrund.net/index.php?title=Aulds_1k_Framework which in turn uses dropper2.0 and apack. Nothing clever here by me, its all done by others.
We used to have a kind of bezier interpolation we used in some of our games which was something like
-a + 9b + 9c -d
where a,b,c,d would be neighbouring points (heights on a height map). The big advantage of using those weights instead of normal bezier ones is
a x 9 = lea eax,[eax+eax*8]
and
-1 + 9 + 9 -1 = 16
so when you divide by 16 to do your final scale it's just
shr eax,4
That made it really fast and really tiny.
I'm in the middle of trying to write tiny bezier triangle patches and that is a very very useful trick. Thanks for sharing it (Karma++)! OK as you shared this I'll share my curve equation for the objects. You'll laugh. Lets say I have 5 points in the object I run t (the upward interpolator) from 0..5 and use the fractional part to interpolate between the two vertices Im currently interested in. Then I square this! Yeah that dumb and simple.
in pseudo code:
interp=fractional(t);
x=lerp(p1x,p2x,t*t);
Almost embarressingly simple. Which is very good at 1k :-).
One slightly cool side effect of this technique is we get more detail where the surface is highly curved (we get the same number of vertices generated between each pair of points so if points are closer together, we get more detail in that area). One downside is no continuity across points, meaning if you have the same x value on the surface on any two points, the interpolator returns a straight line. However for the candlesticks this was actually useful.
-
Quote from: Jim on Today at 06:04:18 AM
Your normals aren't quite on a sphere, but they're damned close, more like an object with 2 circular based cones stuck together on their bases, but who cares because it doesn't matter!
No, they really are on a sphere. Maybe its definition. The normal at any point on a sphere centered at (0,0,0) as you know is just the point itself.
So I centered the object at 0,0,0 (with the y*2-1) and then used the point for the normal. It really is using spherical normals.
I don't see how. For all normals x^2+y^2+z^2 = 1, so given you have 2 points on a circle, the third component ought to be sqrt(1-(s^2+t^2)). I'm willing to be proven wrong though.
Jim
-
Jim,
I don't see how. For all normals x^2+y^2+z^2 = 1, so given you have 2 points on a circle, the third component ought to be sqrt(1-(s^2+t^2)). I'm willing to be proven wrong though.
Yeah I read this like 50 times because its right. I thought am I going mental?
Its probably just definition and some loose wording I used in my article. No my normals arent on the unit sphere. I am using the equation that generates normals for any sphere, inputing my coordinate set. The misunderstanding between us seems to be that all normals are not x2+y2+z2 =1, thats a very special case of a normalised normal, a unit vector. In general the formula for the normal at any point p on a sphere, centred at a point c is:
n = p-c, as you know
and to obtain a normalised version we would do
n'=n/|n|.
I dont do the second step and simply used normals that arent normalised. These are still spherical normals though.
If a sphere is centered at (0,0,0), then the formula reduces to n=p precisely what I'm using which is why I say I'm using spherical normals. The radius of the sphere varies of course : its not a single, definite sphere and I think this is the confusing part about what I wrote as before I said it was lit as a sphere which its not, its lit using the normal equation for spheres which is a little different.
If its y thats confusing here the y*2-1 is simply to do:
a) make (0,0,0) the centre of the object
b) make y the same range as x,z (-1.0..1.0)
Its not meant to generate unit normals. Does this help?
-
++++ Karma. Great posts. I've learned some stuff there I can tell you.
-
Shockwave, now thats the point isnt it? Now if someoine would do the following tutorials for me:
* How to do software mip mapping
* A beginners guide to getting your first basci demo running (download this, install this, include these, use this dev env, hit these keys in it...)
I'd be very happy.
-
That's really great tutorial!
We won't find top stuff like this elsewhere, we are lucky to have Taj here. O0
+karma!
-
Thats a very geenrous comment from the guy who has the highest rated 1k ever on pouet Rbraz. Thanks.
-
As far as the Mip Mapping is concerned, I can help you there Taj.
What kind of tutorial do you want? A full blown one which includes the texture mapping routine or just the mip-mapping bit?
-
For me what I'd like to understand is once you have 2d triangles, how you cheaply do mip-maps (by cheaply I mean efficiently in this case, not small size ;-). I personally know how to transform a bunch of triangles to 2d but maybe others would find this interesting. So how about this, could you do a "here is how to do scan converted mip-mapped triangles given 3d data." What do you think?
-
I'll make this the first thing I do on the new computer tomorrow, but just a few thoughts before I log off for the night about mip-mapping, the technique is fairly simple but typically uses more memory than a regular texture map.
First thing first, in the beginning of the program you'd need to pre-calculate several different sized versions of your texture, it would be best to start off with a big version of your texture and scale down progressively, you could apply some blurr filter to the textures to obtain a similar look to N64 stuff.
Doing the mip map is very simple, you need the area of the triangle you are rendering. If you are culling hidden surfaces, you could be doing it by seeing which way the normal is pointing or by using the cross-product formula.
The cross product will give you the area of the triangle you are rendering. Then you choose the texture map that best fits the size of the triangle.
Benefits are really that it's faster if you are rendering a lot of small triangles because you'll be working with smaller versions of the texture and also you won't suffer dancing pixels when rendering small triangles.
I'll have a think about how I am going to write this tutorial because it could be quite a handful for new programmers if I write it with texture mapped triangles as there would be a lot of concepts to learn in one go.
Probably I'll do something with rectangles in Basic to explain the concept.
-
I'm sure I went through this before...
The area of a 2d triangle on screen in pixels (you know, after projection) is
dx0 = v1.x - v0.x
dy0 = v1.y - v0.y
dx1 = v2.x - v0.x
dy1 = v2.y - v0.y
area = (dx1*dy0 - dx0*dy1) / 2
Use the same equation to work out the amount of texels this triangle covers on the texture map (constant, so pre-calc it, unless your uvs animate)
du0 = v1.u - v0.u
dv0 = v1.v - v0.v
du1 = v2.u - v0.u
dv1 = v2.v - v0.v
texarea = (du1*dv0 - du0*dv1) / 2
Then work out the ratio between the two. You want it to be 1. 1 texel = 1 pixel on screen. Since we're using a ratio, you can drop the divide-by-2s from each of the above equations.
ratio = texarea / area;
Say our uvs are in the range 0-255, then if ratio is 1 or less then just use the 256x256 maximum size texture.
If ratio is 2 then use the 128x128
If ratio is 4 then use the 64x64
If ratio is 8 then use the 32x32
etc.
Where you make the cut-over between the ratios and the texturemaps can be a bit more fine tuned than that. You could cut over at 1.5, 3, 6 instead.
Jim
<edit, code typo>
-
OK that seems very easy now you've explained.
If I want to do perpective correct mip-mapping per pixel, I guess I have to work out the size of a pixel in the texture in x and y at each pixel then divide and use your ratios. Or maybe better work it out at each pixel and interpolate the values in the usual way for triangles. Can you say something on that?
-
eh?
-
In short, I want to calculate the mip-map per pixel, not per triangle...can you comment how its done?
-
Hmmm, not sure I follow you here. For mipmapping, do what Jim's explained. The mipmaps can be generated by taking your original texture then creating a new texture with half the width and half the height and blending/averaging each group of 2*2 texels into 1 on the new texture. Repeat this again and again using the newest texture until you have a texture 1 texel high or wide.
One thing I would recommend (maybe you already do it like this) is don't specify your u/v coords in terms of texels, I tend to use floats u=0.0->1.0 and v=0.0->1.0 to cover the whole texture no matter what size/shape it is (makes it easier to move between the mipmaps). I think this could also be done with fixed point if you wanted.
-
In short, I want to calculate the mip-map per pixel, not per triangle...can you comment how its done?
Very slowly. Without hardware assist. :p
Jim
-
Of course I'm working on this curved surface algo, I'm finding it a good challenge to code :)
Until now, I've the basic pillar shape, next step I'll add curves using an interpolator algo
Yeah, since this is an WIP I'm wasting bytes everywhere :D
-
Thats really spooky to see that exact pillar (the one I was using to debug) being duplicated! Good luck Rbraz. I have a couple more tricks to get the size down than are in the article because they are too difficult and long to explain unless someone is implementing this so when you have the curved part up and running, send me a PM and I'll give you a couple more things I found. Also it would be good if you find any size tricks to share.
-
That looks really nifty Rbraz :) All it needs is a nice marbled texture and you'll be on your way to building some Greek architecture.
-
Thx Shockie!
Thats really spooky to see that exact pillar (the one I was using to debug) being duplicated!
I'm just following the tutorial :)
;Define Pillar = six points
; ----1--- ----2--- ----3--- ---4---- ---5---- ---6----
pillar dd 0.0, 0.0, 3.0, 0.0, 2.0, 1.0, 1.0, 7.0, 3.0, 8.0, 0.0, 8.0
Btw, I have corrected the method to draw the object, I was using a vertex array (big code), now I just compute points and draw the triangle strip.
@Taj: I didn't have any luck with interpolator code until now, and I'm wondering if could explain it with psedo code again, plz ? :)
-
OK the curved interpolation...
Assuming you know the following how to smoothly go around the object and generate triangle strips I think the only question is how to get a curve between the (x,y) coordinates right?
I personally split the code into two routines:
a) a double loop from 0..360 degrees (up and around), steps passed into the routine
b) a routine that takes a model, an up and an around and emits the vertex using opengl calls.
So routine a) looks like:
up=0
do {
around =0
glBegin(GL_TRIANGLE_STRIP)
do { // must go all the way to 360 degrees
sorPoint (modelpointer, around, up) // lower point of pair
sorPoint (modelpointer, around, up+vang) // upper point of pair
around+=hang;
} while (around<=360)
glEnd()
up+=vang
} while (up<360) // note less than...
here is the ciritcal part of the sorPoint, routine b:
...
t = up/360 * numverticesinmodel -1 //get a t value smoothly between 0.0..numvert-1
lowerindex = floor(t) //This is the index of the vertex below t position
upperindex = roof (t) // and above t position
interpval = fractionalpart(t) // we need to interpolate using a number between 0..1
vertexy = linearinterpolate (vertex[lowerindex].y, vertex[upperindex].y, interpval)
vertexx = [b]linearinterpolate[/b] (vertex[lowerindex].y, vertex[upperindex].y, [b]interpval*interpval[/b])
...generate s too (vertexx is the radius, so you know how to do this bit
...glVertex,normal,texture calls
sore point :-) get it :-). OK well no guarantees on that exact pseudo-code but it should help you...
Yes I do know it does a lot of unnecessary calculation, but my version is very very small in the 1k. Also I'm not certain this is the minimum code way. All those floor, roof etc I have written in as few bytes as possible (obviously not using the actual floor function) but its still costly. There are other ways to write this which might be 20-30 bytes less.
Good luck
-
Yeah, I got it working :||
Oh well, my cosine interpolator was broken and I forgot to add the linear interpolate for xz :whack:
Without any optimization, the code to produce this object is 317 bytes packed, so, there's a lot of work to do to make it smaller, but I'm glad with what I have :)
@Taj: The method that I have used is (a little bit) different that you did, and when I got the C version running I'll PM you, just to take a look, maybe there's something useful for you...
Many thanks for this wonderful tutorial O0
++Karma!
-
The .com doesnt run here :-(...do you have an unpacked safe version?
-
@Taj: The method that I have used is (a little bit) different that you did, and when I got the C version running I'll PM you, just to take a look, maybe there's something useful for you...
I was hoping you would say that :-)
-
@Taj: The method that I have used is (a little bit) different that you did, and when I got the C version running I'll PM you, just to take a look, maybe there's something useful for you...
I was hoping you would say that :-)
I'm still hoping :-)