Let's assume you wanna make a nice 64 kb intro with lot of 3d objects. You first try to make use of your common sense and start implementing lot of primitives as cones, planes, boxes, hyperboloids, helixes, and so on (don't forget the torus!). Not bad. You then add basic extrusion and revolution objects; cool! But everything looks so simple, so "intro-like"... You probably think then to implement operators/modifiers to this basic primitives: boolean operations, face extrusion, bend, twist, mirror, and all the others found in your artist's favourite modelling application. However, your intro still looks like ... an intro. You are probably missing organic shapes. So you are doomed to create died 3d man-made scenareos, or pure design abstract scenes. That's quite nice anyway, but you still want to add a human model to your production. You realize that it is basically a symetric model, so you will easilly save half the space. If needed, you can later on use some modifier to deform some verts in order to break the symetry out. You can also use other nice trics, but at some point you want to store a basic 3d mesh of some kind. This is a small article about that last part of the process. es The most simple solution (simple once you know you can use it) is to use subdivision surfaces. Ask your modeller, [s]he probably knows them very well. And that's a good point by it's own. Subdivision surfaces come with most modelling soft packages since Pixar invented them (you will find a nice article in Proceedings of Siggraph 1998). Normally Catmull-Clarck subdivision scheme is used cause it workd on quads (quadrilaterals) that re mose usefull than triangles for modelling real objects. For triangles, you can use Loop subdivision. Both are simple to implement, at least in their basic form (ask google for "Catmul Clark", and just follow the first link, you cannot miss it).

 

For those that never heard about it, here goes a very fast explanation about this subdivision stuff. The idea is to start with a basic, coarse and potentially small mesh representing your 3d model. I will call this 3d model "seed" mesh. This is the only geometry you store in your intro. From this first mesh, a cascade of "subdivision" o refinement steps will follow that will increase the polycount of the model, and that will converge to the resired high-poly and detailed model. For each subdivision step, new vertices and faces are added to the model in a simple way. Of course, in between this steps you can perform additional operations as adding noise, extruding or whatever, what makes evertyhing even more interesting, but let's forget about it for now.

 

This method has some nice mathematical properties. Given an initial starting mesh, the process converges to a BSpline. In practice, this means that the surface will be smooth, with C2 continuity at least (ie, smooth normals) except for some very specific points.

 

The good news is also that the progression of the subdivision is quite intuitive. This translates to an easy-to-use interface for modellers, who can normally model directly on the final model by moving vertices of the seed mesh. Like in splines, changing vertices (control points) of your seed mesh has local influence only, what makes it even easier to use.

 

Finally, you will discover that quite complex models can be created with a relatievely simple seed mesh. For the 195/95/256 64kb intro we used seed models with 800 polys each. And our's was a quite brute force implementation, it can be easilly reduced to half. For Paradise, no model contained more than 200 polys!

 

Now, the most interesting part. How can we store these 800 polys in out exe using as less space as possible? Lot of mesh compression techniques can be used. Have a look out there. BUT, let's do it first in the "demoscener" way, as we did for these intros.

 

Let's use the classic "array of verts, array of indices" technique. For the vertices, the first idea is to use as few bits as possible for the coordinates. Normalizing your object to his boundig box will allow you to store all the coords in 8 bit. Well, it depends on the modell of course, but the lose of acuracy, if noticable, will probably be acepted even by your own modeller. Yeah, the success of the 8 bit precission is surprising, and we didn't discover it until one day before the deadline of Paradise. Anyway, you can of course make it a bit nicer, and use a logarithmic scale if you discover that most of your vertices are just in the center of the bounding box, and just a few of them remain near the borders. Anyway, you have your coords in 8 bit per coordinate (24 bit for the xyz). We can still do something to make the executable compressor happy. As Kb/fr explained, just make deltas of everything. It will not help too much maybe, but it doens't hurt. Our experience says it helps a bit. Something else, you can also deinterlace your array of xyz in three arrays of x, y and z each. Make deltas for each array. Now, if your geometry exporter (from max, maya, whatever) is clever enought and submits vertices to your file format in ordered fashion, jumping from one vertex to the next closest one, you will find your deltas to be small, specially when using 8 bit. Nice! There is another trivial advantage on using three deinterlaces arrays: planar objects (floors, or extrusion objects) will just create some nice dummy arrays.

 

Now, continuing with this brute force way of storing the object, we arrive to the topology - the index arrays. They basically contain the information needed to conect vertices in order to create quads and triangles (yeah, don't forget the triangles, they will probably be very demanded by your artists). There are some easy ways to handle the fucking triangles, just think a bit, but that's another story. Again, the easier way to handle the space used by the indices is to use few bits. 16 should be enought for a seed model. But it is also too many bits, probably. A model with 256 verts should not use more than 32 bit per quad, and a seed model of 800 verts should not use more than 40 bits. Before starting codig bit packing and unpacking code, take into account that trying using deltas is also a good idea here. As before, if the exporter travels you modell in a not random way, you will find close indices in close polygons. So, delta encoding will create quite small values again, and that will probably require even less bits than expected. But, using deltas can potentially create big values, and in general an additional bit will be needed to encode the sign. Our solution was to think in the general case where values will be small. So, what we did was to use delta encoding, and then use two arrays. Onve for the lower 7 bits of the delta values plus one bit of sign, and another array of 8 bit elements with the higher bits of the delta values. Normally this second array contains a few non cero values, if any. And anyway, values in this second array are rarelly bigger than 3 or 4. So, this arrays virtually disapear after compression. Of course, you can just omit those completelly empty arrays (most of them).

 

Well, this is all for this very basic "my-first-3d-compression-tricks". As conclussion, using any subdivision technique plus delta encoding and proper deinterlacing of the data can help you to put at least a few nice 3d modells in your intro. Anyway, make use of your common sense and use procedural techniques for those parts that can be easilly generated, as well as older techniques as extrusions, bevels and so on.

 

Before I forget, don't subestimate your imagination. There is lot of tricks that can be used in combination with this basic ideas explained here, but I will keep those for me, and for those coming to the spanish partyes that can ask me or rgba's members, and more interestingly, share some of their tricks with all us.

 

Hope all this was usefull for somebody. For questions, comments, or whatever, send a mail to iquilezles@hotmail.com