Re[2]: 3D Worlds

[sz <sz@xxxxx>]

Hello Wayne,

четверг, 20 мая 1999 г., you wrote:

WM> OK, Cool. Thanks for this, seems pretty nifty, could you explain what
WM> instructions would be involved and how many, I could work out the misc mips
WM> from this.  I am aware of the server limitations involved with Polygons (the
WM> amount of area taking up by complex FPU's could be devoted to misc chips and
WM> sdram) and think if this alternative methord is more viable in chip usage it
WM> would be good.

WM> From: sz <sz@uc.ru>
>>I could explain it in not more than three pages, if you interested.

WM> Ahhm, I think that would be good, you sort of lost me there a bit.  From the
WM> sounds of it, it sounds simular to a 3D bitmap idea I had.  In the idea I
WM> had a compression scheme for eliminating hollow space and from surfaces,
WM> would that help?  Given the size of the screen and compaction would a 20-bit
WM> processor be able to do a nice 3D shooter, given 32-bits could more be done?
Yes, good ideas come to good brain at the same time. ;)
The very idea is quite simple:
- if you divide whole world into octree, you get a lot of free space
descrived by bigger nodes.
- different parts of octree are in different distance from viewpoint
and you always can render only those nodes, which screen size will be
not less than 1 pixel. Sort of 3D MipMap.

Imagine a cube that has differently colored sides. If you look
straight to it, you see only front side, say, green. If you walk away
from cube it's front view will became smaller and smaller but remains
green. You may look at red upper side, green front and blue left side
at the time on distance they became grey spot. The idea I talk about
is to use 2D mipmaps on each side of octree node, along with
transparency. Transparency easily pops up from the fact that if we
compose an object from sparse solid objects then on distance it
becames transparent - like tree or bush, for example.

Finally, we got an anisotropic space combined from (transparent) cubic
elements. It is anisotropic due to different sides of octree node has
different color.

Each node has 6 sides with unique color and 3 transparency values for
each direction. 2D variant looks like this (one direction):

<---------- solidness: s(transp) := 1-transp
+----+----+ a row color component:             +composed_color:=
| a0 | a1 | A := a1*s(t_a1) + a0*s(t_a0)*t_a1  | (A*s(t_a0)*s(t_a1) +
+----+----+                                    + B*s(t_b0)*s(t_b1)) /2 ;
| b0 | b1 | B := b1*s(t_b1) + b0*s(t_b0)*t_b1  |composed_transp:=
+----+----+ b row color component:             + (t_a0*t_a1+t_b0*t_b1)/2

For a 3D you have 4 rows (and /4 in formulaes) but idea stays the same.

Kajiya equation:

               inf              t
I_ray(t)  = integral ( exp( integral( -alpha(t) * dt)) * I_space(t) *dt)
               0               0

greatly help me in developing this technique.

exp(-alpha(t)*dt) is transparency component fo a piece of space,
I_space(t) - piece of space illumination component.

WM>> OK But what do techniques like 3D bitmaps and the new Voxels
WM> architechures
WM>> take?
WM> Ok. It takes not so much from CPU mights.
WM> Octree-based approach needs division by two when descending tree,
WM> multiplication to determine fitting into level-of-detail, scalar product to
WM> get voxel's visual information and one division for projection.
WM> Division could be non-floating point.
WM> Thanks
Diving a little deeper:
Octree traversal makes a list of visible voxels,
which then can be drawn on screen.

procedure octree_traversal needs center_coords, voxel_size
and pointer for a octree node. It may clip this node against view
frustrum usign any convenient technique. Here it may use sign test for
view frustrum planes, so it needs addititions and compares only. (Am I
right?)
Then it computes on_screen_size :=
distance_to_camera(center_coords)*voxel_size/focus_length, and if
that size is too big (>=2) it tries to descend to children. Center for
a child computed by displacing node_center by
(+-voxel_size/2,+-voxel_size/2,+-voxel_size/2) vector. Here it
needs only division by two and additition/substraction.
If on screen size fits our criteria then it computes voxel_z, voxel_color,
voxel_transparency and screen_coordinates and pushes them, along with
screen_size, into voxel list. voxel_z needs 3x3 matrix and 3D vector
multiply (camera transform), voxel_color and voxel_transparency need each
scalar multiply of 3D vectors and multiply by reciprocal for sum of vector
components.
3D vector used in latter calculations is a vector camera-->voxel_center.

Then you draw them all. ;)

Drawing is simple for sorted by cameraZ list. Draw it going deeper,
skip completely non-transparent parts. (It leads as into occlusion
culling technique, but more on this later.;)

One big disadvantage is the separate draw list, which eats memory.
But I don't know how to bypass it for perspective projection, and,
even worse, such techniques seems to be patented. :(

http://www.uc.ru/~sz/voxels/octree.htm contains messy
feature/deficiencies explanation, some screen shots, better drawn Kajiya
integral, Win32 executables and source (weird one) in C.

Well, resulting letter is very big, just like Jeff ones. ;)

Buy!
 sz                            mailto:sz@uc.ru