How to optimize octree loading time in JavaScript? – Math and Physics

Awtsmoos mentioned:
It ought to be famous that a lot of the mesh is symmetric, being generated with mirror and array modifiers in blender, and the precise uncooked parts are solely only a few, was pondering of solely making octree for these few parts, then one way or the other “instancing” the octree based mostly on the mirror and array modifiers, and “reworking” every occasion with out lowering efficiency, however unsure if that is sensible, and even tips on how to go about it.

Must be the best course.

Should you (can) have instancing, the same old method is to construct the acceleration construction solely as soon as per object. E.g. in case you use the identical stairs 10 occasions within the scene, you construct one native octree for the steps mannequin, after which use that very same octree 10 occasions, identical to it ought to be for the mesh knowledge as nicely.

Then, for the entire scene, you construct one other world octree over all these situations of your fashions. So as an alternative constructing over 10k trinagles, you construct solely over 50 situations for instance.

Discover: This often requires a rework per occasion to assist rotation and scaling if the situations. Mirroring the steps could possibly be applied as a nonuniform scaling for instance.
This implies your octrees are not aligned to the worldwide coordinate system axis as regular.
If the appliance is raytracing, one possibility to do that is to remodel the ray into the native area of the mannequin if we traverse such rework node, the place it is nonetheless axis aligned once more.
If the appliance is vary queries the place the question area is an axis aligned bounding field, you can both rework the areas corners and make a brand new AABB from that (which causes the area to develop in dimension), or you can implement oriented bounding field areas to forestall such development at the price of complexity.

One instance of this method is present raytracing APIs for GPUs, the place they name this ‘Prime Stage Acceleration Construction’ for the worldwide scene octree, and ‘Backside Stage Acc.St.’ for the native mannequin octrees.

It additionally is feasible to assist nesting of a number of ranges, having fashions which encompass many situations themselves.

In addition to saving reminiscence and constructing occasions, this additionally helps with animation, as it’s not wanted to rebuild the acceleration construction. We simply animate the transformation nodes as an alternative. That is an enormous win in efficiency and suppleness.

If we use BVH as an alternative octree, we are able to even assist deformations (character skinning) and not using a must rebuild the tree every body. As a result of BVH isn’t coupled to a worldwide grid, we are able to simply replace its bounding volumes on animation, however hold the topology of the tree as is.

Discover: When you implement assist of such transformation nodes, we free the octree assure of non overlapping bounds. This implies we now have to vary traversal algorithms of a degree question to now assist the traversal of a number of kids, as their bounds can overlap (which is also already true if we use a ‘free’ octree).

Thus, we are able to say that in apply BVH typically is the higher acceleration construction than octree attributable to flexibility.

B”H

@JoeJ Hello thanks for the response.

Is there any working examples of something like this on-line, concerning both BVH or instancing octree? I solely have a static home mesh that I need to verify collision with a capsule solely. Additionally I need to have the ability to assist a much bigger world, is there some form of method to this?

I used to be initially pondering of splitting up your entire world right into a 3D array, with every block within the array representing a certain quantity of space [similar idea to an octree but different in a few ways], then when the ccharacter strikes every body, the one calculation that is accomplished is to around the place of the motion, and verify which part[s] of the 3D array it is colliding with, and maybe make an octree inside every part for the vertices in it and verify them, or make nested 3D arrays inside every 3D array that might include some vertices.

However I used to be pondering that if it is a good thought, it has in all probability been accomplished earlier than, and the truth that I have not been capable of finding anything about it would suggest it is not a good suggestion, what do you concentrate on it, is it sensible, are there any working examples of it and so on.?

Awtsmoos mentioned:
Is there any working examples of something like this on-line, concerning both BVH or instancing octree? I solely have a static home mesh that I need to verify collision with a capsule solely. Additionally I need to have the ability to assist a much bigger world, is there some form of method to this? I used to be initially pondering of splitting up your entire world right into a 3D array, with every block within the array representing a certain quantity of space [similar idea to an octree but different in a few ways], then when the ccharacter strikes every body, the one calculation that is accomplished is to around the place of the motion, and verify which part[s] of the 3D array it is colliding with, and maybe make an octree inside every part for the vertices in it and verify them, or make nested 3D arrays inside every 3D array that might include some vertices. However I used to be pondering that if it is a good thought, it has in all probability been accomplished earlier than, and the truth that I have not been capable of finding anything about it would suggest it is not a good suggestion, what do you concentrate on it, is it sensible, are there any working examples of it and so on.?

One of the best instance is physics engines.
I do not know the way far we might get utilizing JavaScript attributable to efficiency, however possibly there are net physics engines / backends / wrappers you can search for or use.

Relating to your thought of a high stage uniform grid, i just lately labored on simply that.
My world isn’t primarily comprised of situations of (small) objects, however from an enormous single static mesh. To assist streaming open world, i divide the mesh into uniform grid cells.
So i can stream simply the tiles across the present participant place. And now i needed so as to add assist for this to the Newton physics engine i am utilizing.
The issue is that physics wants some adjacency info throughout the boundary of cells. In my case, Newton must know the face regular of the adjoining face of an edge. However this face could also be in one other cell, so i needed to hack the Physics engine a bit to make this work by including further boundary face normals.

It labored, and the result’s that the Physics engine builds one BVH for every cell, simply because it usually does utilizing one BVH per mannequin.
The physics engine additionally makes use of some high stage acceleration construction, with all these sub BVH fashions changing into leafs. Simply as i had proposed above.
As a result of my cells type an everyday grid, i’d work on changing this default high stage acceleration construction with a easy common grid for higher efficiency sooner or later.

So sure, i feel your concepts make whole sense. However it relies upon.
In case your world is sufficiently small you possibly can have all of it in reminiscence, and you’ll haven’t any instancing of fashions, no animations or dynamics, then there could be no motive to combine totally different acceleration constructions.
You can simply use one single octree for the entire thing. And attributable to decreased complexity, this straightforward answer ought to be quicker than mixing common grids with octrees.
Individuals typically suppose they might get some speedup by utilizing a ‘quick’ common grid on high, however that is not usually true in my expertise.
So the higher causes to make use of such blended approaches is streaming, instancing, compression, animation assist, and so on. Simply to make that clear.

I hope you could find some physics engine that will help you out, as that is a whole lot of work and a real efficiency drawback.
Even in case you do not want fancy physics simulations, collision detection is motive sufficient to make use of one.

B”H

@JoeJ Hello good to listen to again, that is cool that you just simply labored on an identical method.

I might very very like to not use a physics engine, as:

I need to perceive how all the pieces works, and be capable of repeat it and educate it

I need to hold it gentle weight, presently it really works at full fps even on an outdated android mannequin and I want to proceed that method

The octree works advantageous by way of efficiency, the issue is simply the preliminary loading.

I have not absolutely understood the code but, however I am fairly certain it rebuilds at the least a big portion of it each time it provides new triangles and so on., which possibly is what’s slowing it down.

Is there any option to commerce off RAM for quicker preliminary computing time?

Awtsmoos mentioned:
I need to perceive how all the pieces works, and be capable of repeat it and educate it

Properly, that is a very good motive to do it your self. ; )

Awtsmoos mentioned:
Is there any option to commerce off RAM for quicker preliminary computing time?

You imply you desire a smaller tree? So downloading it’s quicker?
Otherwise you need quicker construct of the tree, since you do not obtain / precompute in any respect?

One thought could be to precompute the tree, however don’t retailer bounding packing containers with it, which take essentially the most area.
Then calculate the bounding packing containers after the obtain which is far quicker than constructing the entire tree.
(Assuming you utilize bounding field per node in any respect.)

Some typical compression library (zlib and so on.) may assist as nicely.

B”H

@JoeJ hello good to listen to again, thanks for the thought

At first I began by making an attempt to export the entire tree as a JSON string, however that took up 230mb for even a fundamental mannequin, by way of textual content. I am guessing there are different methods of exporting it utilizing bytes to characterize the triangles and sub timber to scale back area, however I have not discovered any examples, I suppose I can experiment with it however I haven’t got a lot expertise constructing binary information, particularly with nested arrays

I am fairly certain one has to have break up the file up into sections, with every part having header info concerning the part earlier than and after it, or one thing like that. Even so it will be ideally suited to only load the 2mb blender file then apply the modifiers with JavaScript utilizing jsblend then compute the octree then, however then we could also be again to the sooner dialogue concerning instancing a number of octrees based mostly on array and mirror modifiers and so on.

Anyhow concerning loading it with out the packing containers would I additionally export all the subtrees, however containing solely triangles and different subtrees, then basically run the “addTriangle” methodology for every triangle when loading? If that’s the case I can strive it out however I believe it might nonetheless take a number of time and should or could not crash the web page, however this is the code I am going off of https://github.com/yaakovyitzchak/reebooyaw/blob/major/Octree.js

Awtsmoos mentioned:
Even so it will be ideally suited to only load the 2mb blender file

Oh, if the geometry knowledge is that small, i don’t see a necessity for instancing in any respect. To make some guess, i might say the octree ought to be one thing like 10 or 20mb at most. Relies upon ofc, however 230mb appears simply method an excessive amount of!

Utilizing binary information could be the very first thing to strive. Assuming the worst case, JSON textual content file makes use of two bytes per character to assist some unicode. A floating level quantity might have 6 digits, which is 12 bytes vs 4 bytes with a binary file.
However even when we are able to cut back the dimensions to 230/3, it nonetheless feels very giant to me.

The following step could be to have a look at the octree knowledge construction itself.

Awtsmoos mentioned:
this is the code I am going off of https://github.com/yaakovyitzchak/reebooyaw/blob/major/Octree.js

I am not good with JS, however i make some assumptions:

The octree provides a triangle to any node it intersects. So we are able to assume every triangle is possibly in 4 leaf nodes on common. So we duplicate the information 4 occasions.
I am unsure if the nodes simply retailer an index to a triangle array (could be good), or in the event that they retailer precise duplicates of the entire triangle knowledge (e.g. 9 floating level numbers for the vertex factors).
Should you can reply it is the latter, we now have the explanation of the massive reminiscence necessities. And it’s best to change this to make use of the previous methodology as an alternative.

The octree shops bounding field per node. However as a result of this isn’t a free octree (the place every triangle goes into just one node, requiring overlapping bounds), this isn’t wanted.
As a substitute, you possibly can calculate the bounding field throughout traversal from the grid coords and tree stage.
This provides some complexity to the traversal code and in addition makes issues like raytracing much less environment friendly, but when reminiscence utilization is your drawback, i might definitely do that. As a result of it reduces reminiscence bandwidth, it could possibly be even quicker.

It is not clear to me what is the stopping standards of the octree construct course of.
There are some choices:
Hold subdividing the tree till no node has greater than X triangles. (Which could go without end if the geometry has many triangles at a single spot.)
Or, set a most of N tree ranges upfront, and cease subdivision after that, irrespective of what number of triangles could find yourself in a single node. (As a result of your geometry is static, you possibly can tehn discover a good reminiscence / efficiency compromise for N with trial and error.)

It is not clear to me if the octree shops triangles in inner nodes or simply in leaf nodes. Explaining these choices:
Storing all triangles in leaf nodes is easier, nevertheless it solely works nicely if all triangles are of comparable dimension.
In case you have some very giant triangles within the scene, a single giant triangle would go into a complete lot of leaf nodes, which prices reminiscence and turns into inefficient. Then it is higher to place it into inner nodes, as a result of these nodes have a lot bigger cell bounds to resolve this drawback.

Really i assume you could find yourself implementing your personal octree knowledge constructions, construct course of and vary question / raytracing traversal logic. That is some work, so the above factors are in all probability the principle arguments to bear in mind.
It is not simple to seek out good tutorials on the topic, however very simple to seek out unhealthy ones.

I simply keep in mind this one, which absolutely is nice as a result of the man is professional and pioneer of realtime raytracing: https://jacco.ompf2.com/2022/04/13/how-to-build-a-bvh-part-1-basics/
It is about BVH, dynamic senes, and absolutely overkill on your wants, however could also be value studying to seize some basic ideas.