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.