## Tuesday, February 08, 2005

### OpenGL and Direct3D are for sissies...

...real men do their 3-d graphics in PostScript! :-)

What the Cantor dust is in one dimension and the Sierpinski carpet in two, the Menger sponge (also known as the Sierpinski cube) is in three dimensions. Start with a cube and divide it into 3*3*3 smaller cubes; then remove those that do not touch any of the edges of the original cube. This leaves 20 out of the 27 smaller cubes. Now the same step can be performed on them, resulting in an object composed of 400 even smaller cubes, and so on. The volume of the object tends towards zero, but its surface increases beyond all bounds. The picture shown here is the object obtained after we perform this step four times.

Anyway, I thought it would be fun to draw this in PostScript. It doesn't have any particular support for 3-d graphics, so we have to project things by ourselves. The surface of the sponge consists of a number of small squares; we just have to be careful to draw them in the correct order, so that the ones which appear closer to the viewer will be drawn last (and thus won't be obscured by other things). The correct order depends on the angle from which we are looking at the object; the one used by the showCube procedure below is suitable for the particular angles (lat and lon) used, but if these were changed considerably, the procedure might need to be rearranged a bit.

%%BoundingBox: 109 199 495 600

/n 4 def   % approximation level of the fractal
/xyColor { 1 0.5 0.5 setrgbcolor } def
/xzColor { 0.5 1 0.5 setrgbcolor } def
/yzColor { 0.5 0.5 1 setrgbcolor } def
/distanceFromCamera 2.5 def
/lon 50 def /lat 36 def  % to rotate the object
/scale 600 def % larger values = larger object

/pow { % a b pow -> a^b
2 dict begin /b exch def /a exch def
1 { b 0 le { exit } if
a mul
/b b 1 sub def
} loop
end
} def

/isPresent { % x y z isPresent --> true/false
20 dict begin
/z exch def /y exch def /x exch def

x 0 lt y 0 lt or z 0 lt or
x n3 ge or y n3 ge or z n3 ge or
{ false }
{
{   n 0 le { true exit } if
x 3 mod 1 eq { 1 } { 0 } ifelse
y 3 mod 1 eq { 1 } { 0 } ifelse
z 3 mod 1 eq { 1 } { 0 } ifelse
/x x 3 idiv def
/y y 3 idiv def
/z z 3 idiv def
/n n 1 sub def
} loop
} ifelse
end
} def

/map3dTo2d { % x y z map3dTo2d --> xMapped yMapped
30 dict begin
/zi exch   n3 2 div  sub n3 div def
/yi exch   n3 2 div  sub n3 div def
/xi exch   n3 2 div  sub n3 div def

% Rotate by 'lon' degrees around the z-axis.
xi lon cos mul   yi lon sin mul   sub  % new xi
xi lon sin mul   yi lon cos mul   add  % new yi
/yi exch def /xi exch def
% Rotate by 'lat' degrees around the y-axis.
xi lat cos mul   zi lat sin mul   sub  % new xi
xi lat sin mul   zi lat cos mul   add  % new zi
/zi exch def /xi exch def
% Project.
yi xi div scale mul
zi xi div scale mul

end
} def

/xyfacet {
30 dict begin
/zi exch def /yi exch def /xi exch def
newpath
xi yi zi              map3dTo2d moveto
xi yi 1 add zi        map3dTo2d lineto
xi 1 add yi zi        map3dTo2d lineto
xyColor fill
end
} def

/xzfacet {
30 dict begin
/zi exch def /yi exch def /xi exch def
newpath
xi yi zi              map3dTo2d moveto
xi yi zi 1 add        map3dTo2d lineto
xi 1 add yi zi        map3dTo2d lineto
xzColor fill
end
} def

/yzfacet {
30 dict begin
/zi exch def /yi exch def /xi exch def
newpath
xi yi zi              map3dTo2d moveto
xi yi zi 1 add        map3dTo2d lineto
xi yi 1 add zi        map3dTo2d lineto
yzColor fill
end
} def

/showCube
{
30 dict begin

0 1  n3 1 sub {
% We will now show level r
% (z-coordinate from r to r+1).
/r exch def

% First show the bottom facets.
0 1  n3 1 sub  { /yi exch def
0 1  n3 1 sub  { /xi exch def
xi yi r 1 sub isPresent
xi yi r isPresent
not and { xi yi r xyfacet} if
} for } for

% Then show the facets which are not
% perpendicular to the z-axis.
0 1  n3  { /yi exch def
n3 -1 0  { /xi exch def
xi yi 1 sub r isPresent
xi yi r isPresent
not and { xi yi r xzfacet } if
} for
n3 -1 0  { /xi exch def
xi yi r isPresent
xi 1 sub yi r isPresent
not and { xi yi r yzfacet } if
} for
} for

% For the last (topmost) layer,
% also show the top facets.
r  n3 1 sub  eq {
0 1  n3 1 sub  { /yi exch def
0 1  n3 1 sub  { /xi exch def
xi yi r isPresent
{ xi yi r 1 add xyfacet } if
} for } for
} if
} for

end
} def

gsave
0.2 setlinewidth
/n3 3 n pow def
% Center it on the A4 sheet of paper.
0.5 595 mul 0.5 842 mul translate
showCube
grestore

showpage

You can copy the above code into a file and send it to your favourite PostScript printer, or open it in a viewer such as Ghostview.

For a level-4 sponge, such as we see in the picture above, this draws 168192 facets. When I tried converting this PostScript file to PDF, the resulting PDF file was several megabytes long, because PDF is not really a programming language with loops and so forth, and the PDF file simply contained all the objects drawn by the above program. However, of these 168192 facets, most aren't really visible in the end because they are obscured by other facets. I wrote a C++ program to determine which ones are completely obscured by others and may be removed; only approx. 22000 facets were left, and the image when rendered at 1200 DPI was completely unchanged; the resulting PDF file was only about 400 KB long.

P.S. Since the title mentions sissies, this comic should not be missed.

Bo said...

This is a complete surprise, a fan of history books who can program in PostScript. None of my classmates at the faculty for physics knew this language.

Sunday, November 05, 2006 10:46:00 AM

In fact I think that if the same experiment were repeated at the CS dept., the results wouldn't be much different :) Which is not suprising, as it's a completely useless language, unless you need to talk to printers or something like that (which most people don't). I learnt it mostly because it can be quite handy for preparing illustrations for use with TeX. And it's also interesting as a kind of curiosity due to its stack-based paradigm.

Incidentally, I would guess that many physicists are probably fond of Hewlett-Packard calculators, which (if I understand correctly) lean heavily on postfix notation and stack-based processing. If so, they might find PostScript quite congenial to their tastes. :)

Sunday, November 05, 2006 11:38:00 AM
Bo said...

Yes. :) HP calculators are neat also because of this special notation called RPN. Not all of them implements it, and I don't think HP makes such calculators any more. I have a bit older model 32SII that has RPN and I am fond of it.

So you are a TeXmaster too, another surprise. What is your formal education anyway; and what do you do for a living? You don't have to answer these questions of course, I am just growing very curious.

Well, good luck.

Sunday, November 05, 2006 9:49:00 PM