a file format to compress a triangle soup based on an octree:
- first convert the coordinates to integers - so some quantization
- eg: convert to millimeter quantized integer positions
- best idea is to find the best tighest fitting bounding box (smallest volume)
around all the points and then make the axes be aligned to this box
and for the model store the details of this coordinate system
- the information about this given coordinate system is really just a matrix
and can encapsulate the rotation to this bounding box as well as what the
units of the scaling
- if the coordinate system is just a matrix, the bounding box can be inferred
to be starting at the origin and extending to a given coordinate, such as a
vector called 'extents', so the bounding box info only requires a vector more.
- the center is at extents / 2
- a bound sphere at this center will have radius of the largest of extents.x, y or z
- for example a model which fits within a meter cubed space, when quantized to mm will
have x,y,z parameters from 0 to 1000. therefore 10-bits per x,y,z is
already enough, so could just store each vertex position with a
32-bit value. However we can even do much better than that.
- consider the space that is 1024x1024x1024, may be about 1/8 of the
vertexs will be in one 512x512x512 octant, another 1/8 in another and
so on. By putting the vertexes in to buckets by octant, the first
bit of each coordinate is implied. So then only need 9bits per coord
or 27bits per vertex position to store where within the octant it is.
- This can be repeated down to 256x256x256 sub-octants and so on until
there are only a few vertexs in the given octant that the cost becomes
worth just storing the bits instead of through it being implied.
- This implied position by where the vertex is inside the octree saves
a large explict cost of storing position bits, so could reduce the
cost down to a quite small bit cost per vertex if the vertexes are
sufficiently dense. If the vertexes are quite sparse, then savings
will be less. It might be possible to have a cost function which can determine
which way is better, and then at some level of the octree switch to the other mode.
- octree storage strategies:
- an octree is a tree, typically a tree implies pointers
- pointers are nice in that when in memory it is simple to navigate the tree,
the pointer is the memory address of the child node
- one disadvantage of using pointers is that the memory structure can't be
serialized and deserialized to a file for example without having to fix-up
or initialize these pointers as the relative address where the tree exists
in memory could be different (and similarly if trying to share between processes
in shared memory, the in-memory representation can't be used across processes
is the shared memory is mapped at different addresses).
- another approach is using indexes instead of pointers. The index is an offset from
some base address where an array of nodes exists. This makes serialization and
de-serialization easier (and using from shared memory).
- an advantage in using pointers over indexes is that the nodes don't have to be
from contiguous memory, so it is easier to add and remove nodes dynamically which
is better for editing or where the octree needs to be modified dynamically
- but with indexes again if we assume we aren't adding and removing points,
it may be possible to infer what the indexes will be. Usually a parent node will
be at one level of the octree and the children nodes are all at the next level of the
tree down. By convention the indexes of the children are all one after the next in
the level below, so no need to store what the index of each is, it is enough that the
node has what the first child's index is. And this can also be inferred if you were to
walk the tree and count all the children nodes of the nodes at the given level up to
the node you are on to work out the index offset of the child level. So as you can see
in storage, there is no need to store indexes in the tree, only the information needed
to show essentially how occupied octants are. This is usually referred to as the octant
masks.
- lets go back to our 1m cube containing vertexes with 1mm resolution of the coordinates.
we need 10bits per coordinate. That would be 30bits per vertex. But worse case if we
store a mask at the first level, that is 1 byte and with that 1 byte we then have 8 buckets
of vertexes now only with 27bits per vertex. At the next level, worst case we need 8bytes
for 8 masks, and have 64 buckets, now only needing 24bits per vertex. We can repeat to
1+8+64 bytes for masks and then buckets of vertexes only with 21bits each. Next is
1+8+64+512 = 585 bytes worst case (even distribution of vertexes) for masks, and lots of
buckets of vertexes, and then the cost is only 18bits per vertex. One more level down
we have 1+8+64+512+4096 = 4681 bytes + 15bits per vertex. So lets call that 16bits per
vertex instead of 32bits. So with 2000 vertexes, it would cost 8000 bytes if stored using
plain 32bits per vertex, but if we use the octree masks we have a cost of 4681 + 4000 which
is 8681 bytes, so actually at the 2000 vertex count, it is not worth it to go to that level.
Reducing to the 24bit case, we would need 9 bytes of masks, plus 6000 bytes for 2000 vertexes
using 24bits. This is a savings. If instead the vertex count was 3000, then the 32bit cost
would be 12000 bytes, the 24bit cost would be 9 + 9000, the 16bit cost would be 4681 + 6000
which would be 10681. The 24bit case is still the best. With 5000 vertexes, 32bit cost would
be 20000, 24bit would be 15009, the 16bit cost would be 14681, so it is about at the 5000
count that it becomes worth using a deeper depth.
The exact cost may depend on the distribution of the vertexes, as the 4681 bytes overhead
cost of using the octree to a 16bit depth depends on the distribution and this could
be reduced if there are octants which don't contain vertexes (probably quite likely for most
surface modelled models - there is no need to have interior points which can't be seen)
- other uses
- collision geometry - collisions might be easier against a octree
- path finding - although 2d better
- special cases
- 2.5D - perhaps special cases could use a quadtree instead where the mesh is like a terrain
- most objects if viewed from front/back, top/bottom, left/right have depth from each of these
perspectives and have a silluette. This depth map and silluette could be encoded with an octree.
Then the corresponding octree derived from this. This is not 100% correct in that there are some
interior geometries which won't be captured by this, so some loss of information, but this
probably is not an issue if the given object can only be viewed from outside of it's bounding
volume. The interior geometries that would be lost probably could only be really seen or
appreciated if viewed from with in the bounding volume of the object.
This is quite a different appoach as it isn't proposing encoding vertex information more
efficiently, but without a mesh, the mesh would need to be reconstructed but no vertex indexes
and triangles are needed, it is created.
traditional 3d triangle rendering, however the twist is
to use an octree that references the vertexes and triangles
for doing a front to back sorting and a quadtree for doing
occlusion testing
vertex list -> xyz,uv,normal,triangle refs
triangle list -> 3 vertex indexes, real normal, render normal
poly list -> triangle list & texture info
idea
build octree until 1 or 0 vertex in the octant
render octree front to back, iterate the triangle refs for the current vertex and
then store in the occlusion quadtree the area of triangles drawn that falls within
the projection of the octree octant projected on the screen. Ignore octants that
are fully occluded. Use z-buffer for resolving z-order of triangles sharing same
vertex and for combining or post-processing.
