Author Topic: Tiny 1k grail  (Read 17778 times)

0 Members and 1 Guest are viewing this topic.

Offline rdc

  • Pentium
  • *****
  • Posts: 1495
  • Karma: 140
  • Yes, it is me.
    • View Profile
    • Clark Productions
Re: Tiny 1k grail
« Reply #20 on: November 07, 2006 »
Some good information there.

Offline Jim

  • Founder Member
  • DBF Aficionado
  • ********
  • Posts: 5301
  • Karma: 402
    • View Profile
Re: Tiny 1k grail
« Reply #21 on: November 07, 2006 »
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
Challenge Trophies Won:

Offline taj

  • Bytes hurt
  • DBF Aficionado
  • ******
  • Posts: 4810
  • Karma: 189
  • Scene there, done that.
    • View Profile
Re: Tiny 1k grail
« Reply #22 on: November 07, 2006 »
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:
Code: [Select]
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.
« Last Edit: November 07, 2006 by taj »
Challenge Trophies Won:

Offline Jim

  • Founder Member
  • DBF Aficionado
  • ********
  • Posts: 5301
  • Karma: 402
    • View Profile
Re: Tiny 1k grail
« Reply #23 on: November 07, 2006 »
Quote
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
Challenge Trophies Won:

Offline taj

  • Bytes hurt
  • DBF Aficionado
  • ******
  • Posts: 4810
  • Karma: 189
  • Scene there, done that.
    • View Profile
Re: Tiny 1k grail
« Reply #24 on: November 07, 2006 »
Jim,

Quote
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?

« Last Edit: November 07, 2006 by taj »
Challenge Trophies Won:

Offline Shockwave

  • good/evil
  • Founder Member
  • DBF Aficionado
  • ********
  • Posts: 17414
  • Karma: 498
  • evil/good
    • View Profile
    • My Homepage
Re: Tiny 1k grail
« Reply #25 on: November 07, 2006 »
++++ Karma. Great posts. I've learned some stuff there I can tell you.
Shockwave ^ Codigos
Challenge Trophies Won:

Offline taj

  • Bytes hurt
  • DBF Aficionado
  • ******
  • Posts: 4810
  • Karma: 189
  • Scene there, done that.
    • View Profile
Re: Tiny 1k grail
« Reply #26 on: November 07, 2006 »
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.
Challenge Trophies Won:

Offline Rbz

  • Founder Member
  • DBF Aficionado
  • ********
  • Posts: 2757
  • Karma: 493
    • View Profile
    • https://www.rbraz.com/
Re: Tiny 1k grail
« Reply #27 on: November 07, 2006 »
That's really great tutorial!

We won't find top stuff like this elsewhere,  we are lucky to have Taj here.  O0

+karma!
Challenge Trophies Won:

Offline taj

  • Bytes hurt
  • DBF Aficionado
  • ******
  • Posts: 4810
  • Karma: 189
  • Scene there, done that.
    • View Profile
Re: Tiny 1k grail
« Reply #28 on: November 07, 2006 »
Thats a very geenrous comment from the guy who has the highest rated 1k ever on pouet Rbraz. Thanks.
Challenge Trophies Won:

Offline Shockwave

  • good/evil
  • Founder Member
  • DBF Aficionado
  • ********
  • Posts: 17414
  • Karma: 498
  • evil/good
    • View Profile
    • My Homepage
Re: Tiny 1k grail
« Reply #29 on: November 09, 2006 »
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?
Shockwave ^ Codigos
Challenge Trophies Won:

Offline taj

  • Bytes hurt
  • DBF Aficionado
  • ******
  • Posts: 4810
  • Karma: 189
  • Scene there, done that.
    • View Profile
Re: Tiny 1k grail
« Reply #30 on: November 09, 2006 »
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?
Challenge Trophies Won:

Offline Shockwave

  • good/evil
  • Founder Member
  • DBF Aficionado
  • ********
  • Posts: 17414
  • Karma: 498
  • evil/good
    • View Profile
    • My Homepage
Re: Tiny 1k grail
« Reply #31 on: November 09, 2006 »
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.
Shockwave ^ Codigos
Challenge Trophies Won:

Offline Jim

  • Founder Member
  • DBF Aficionado
  • ********
  • Posts: 5301
  • Karma: 402
    • View Profile
Re: Tiny 1k grail
« Reply #32 on: November 09, 2006 »
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>
« Last Edit: November 10, 2006 by Jim »
Challenge Trophies Won:

Offline taj

  • Bytes hurt
  • DBF Aficionado
  • ******
  • Posts: 4810
  • Karma: 189
  • Scene there, done that.
    • View Profile
Re: Tiny 1k grail
« Reply #33 on: November 10, 2006 »
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?
Challenge Trophies Won:

Offline Jim

  • Founder Member
  • DBF Aficionado
  • ********
  • Posts: 5301
  • Karma: 402
    • View Profile
Re: Tiny 1k grail
« Reply #34 on: November 10, 2006 »
eh?
Challenge Trophies Won:

Offline taj

  • Bytes hurt
  • DBF Aficionado
  • ******
  • Posts: 4810
  • Karma: 189
  • Scene there, done that.
    • View Profile
Re: Tiny 1k grail
« Reply #35 on: November 10, 2006 »
In short, I want to calculate the mip-map per pixel, not per triangle...can you comment how its done?
Challenge Trophies Won:

Offline Stonemonkey

  • Pentium
  • *****
  • Posts: 1315
  • Karma: 96
    • View Profile
Re: Tiny 1k grail
« Reply #36 on: November 10, 2006 »
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.

Offline Jim

  • Founder Member
  • DBF Aficionado
  • ********
  • Posts: 5301
  • Karma: 402
    • View Profile
Re: Tiny 1k grail
« Reply #37 on: November 10, 2006 »
Quote
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
Challenge Trophies Won:

Offline Rbz

  • Founder Member
  • DBF Aficionado
  • ********
  • Posts: 2757
  • Karma: 493
    • View Profile
    • https://www.rbraz.com/
Re: Tiny 1k grail
« Reply #38 on: November 12, 2006 »
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

Challenge Trophies Won:

Offline taj

  • Bytes hurt
  • DBF Aficionado
  • ******
  • Posts: 4810
  • Karma: 189
  • Scene there, done that.
    • View Profile
Re: Tiny 1k grail
« Reply #39 on: November 12, 2006 »
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.
Challenge Trophies Won: