Pete <Pet### [at] nymaliasnet> wrote:
:         Something about how pov handles meshes is realy efficient
: time-wise as well as memory-wise.

  If you are interested on how povray can do it, here is some explanation
(AFAIK):

  - Memory usage:

  Firstly, the mesh is kept in memory in a quite compact format. The structure
of this format is very similar to the mesh2 format in megapov, that is, the
vertex points and triangles are kept separately. If more than one triangle
share a vertex point, this point is stored only once. I use this technique
myself in the PCM format.
  (Of course the actual values are kept in floating point format in memory,
so each one takes about 8 bytes of memory in most systems. The triangles are
groups of 3 (normal triangle) or 6 (smooth triangle) indices, which are
probably 4 bytes each in most systems.)
  I haven't calculated any specific values, but a regular mesh in povray
format will take probably less than 1/10 or 1/20 or even less memory compared
to the file size where the mesh is in ascii format (supposing that the file
contains the entire raw mesh, not one that calculates the mesh).
  The worst case is when all triangles are separate, ie. none of them share
any point with other triangles (this may be the case with, for example, the
leaves of a tree where each leaf is one triangle).
  The more vertices a triangle shares with other triangles, the less memory
it will take.

  Another great memory optimization happens when a mesh is copied (I think
this is the most known one).
  When a mesh is declared and then several copies of this mesh identifier
are used, only one copy of the mesh is kept in memory and all those
copies just refer to it. The size of one of these references is very minimal
(something like 100 bytes or so; I don't know the exact amount).
  This means that you can have a 10 Megabytes big mesh and create 100 copies
of it an still it will take 10 Megabytes of memory (and some bytes more).

  What I don't understand why this copy optimization is not made with other
objects as well (like big CSG and so on).

  - Rendering speed:

  The rendering speed optimization of a triangle mesh in povray can be quite
marvelous.
  You can test it:
  Make an object (eg. a sphere) made with about 10 triangles and render it.
  Then make the same object (so that its size on screen is approximately the
same) with about 100 triangles, render it and compare the rendering time.
  Then make it with 1000 triangles. Then with a million triangles.

  You will be surprised how small the rendering time increase is. The sphere
made with 1 million triangles renders surprisingly fast compared to the
sphere made with 10 triangles (of course the parse time increases a lot, but
that's normal and not important here).
  I have tested this once but I don't remember the results. I think that the
sphere with 1 million triangles didn't take even twice the time the sphere
made of 10 triangles took.

  In your case rendering more than 23 millions of triangles doesn't take much
more than rendering just some thousands of them (or some hundreds). That's
why you can make so big "landscapes" with it without the rendering time going
to the roof.

  As far as I know, the trick here is using a specialized structure: An
octree.
  An octree splits the mesh boundary (which is a box) into 8 equally sized
blocks (also boxes). Then each one of them is split into 8 equally sized
blocks as well, and so on.
  When a ray hits the boundary box of the mesh, then povray looks which one
of those 8 blocks did it hit. Then it concentrates on that block and forgets
the others. This means that in the average it can forget about 87.5% of the
triangles (eg. if there are 1 million triangles in the mesh it can forget
about 875000 of them).
  After this it looks which sub-block did it hit. Again, it can forget about
87.5% of the triangles of that block when it goes to the sub-block.
  And so on. It does this until it finds a block that is empty (so that it
can just forget it and follow the ray to the next block it hits) or it only
has one triangle. Calculating the intersection of the ray with this one
triangle is easy and fast (if the ray didn't hit the triangle it just continues
as if the block was empty).

  The fact that it can forget about 87.5% of the triangles each time it goes
to a sub-block makes it extremely fast. The principle is the same as in
the binary search of tables, but faster (the binary search forgets only
50% of the values when it takes a step).
  Of course the number of blocks in the entire mesh increases when the number
of triangles increases, but the number of blocks increases very slowly
compared to the increase of triangles.

-- 
main(i,_){for(_?--i,main(i+2,"FhhQHFIJD|FQTITFN]zRFHhhTBFHhhTBFysdB"[i]
):_;i&&_>1;printf("%s",_-70?_&1?"[]":" ":(_=0,"\n")),_/=2);} /*- Warp -*/

Post a reply to this message