Hi.
I have a task to build maximum AABB (one or more) that will best fill the inside of a 3D model.
How to do it?
Need to build at least one AABB, and it's good.
If anyone has any ideas, and better some code, share please!!
Calc maximum INNER AABB
AABB (one or more) that will best fill the inside of a 3D model
If the model can be any arbitrary shape, then an infinite number of infinitely small boxes would be "best." You need to better describe constraints on "best fill" to get a better answer.
That isn't a homework problem, is it?
Author
For what use case you need those?
for occlusion culling.
If the model can be any arbitrary shape, then an infinite number of infinitely small boxes would be "best." You need to better describe constraints on "best fill" to get a better answer.
If I say "maximum aabb", it does not mean that I need small boxes, ok?
if model very complex, it needs in several boxes, than one.
Well I got a little idea that seems utilizable (I may be incorect in something but I think the general idea is maintainable to the goal).
First, this process is done offline, so you may consider more computational expense without worries.
The idea:
-Compute axis aligned bounding box.
-From every corner of AABB, cast a vector between the corner and vertex of a triangle that is visible from the corner (consider winding. without occlusion, as for not convex shapes, the furthest visible one should be taken for total absolute minimum)
- this vector will yield Axis Aligned subtract from AABB, toward the current maximal subtract registered
- the minimums left against all the corners is axis aligned box that is contained in entire shape
a few little facts
- totaly contained box may not be the best occluder if only certain angles of observation matter
- the "inner BB" should maybe not be axis aligned- consider a big thin plate at 45 degrees in object space- axis aligned inner BB would only be silly thin stick as the plate is thin.
- if the shape is convex, you may consider a little deviation of "axis separation theorem", but this would demand a rasterizing method in your offline computation, what complicates finding the "inner BB", but also allows you to overcome Axis Align issue, so you might find arbitrary biggest cube in the shape
https://mediatech.aalto.fi/~ari/Projects/OSPS/
Not aabb's but something better with similar triangle counts.
Author
I don't really understand your idea...The idea:
You suggest to reduce AABB, checking every corner of AABB?
It's good idea, but it looks difficult to implement.https://mediatech.aalto.fi/~ari/Projects/OSPS/
Not aabb's but something better with similar triangle counts.
I have a task to build maximum AABB (one or more) that will best fill the inside of a 3D model.
Even without a formal prove, I would guess, that you have a np-hard problem here (optimization algorithm are always dangerous). Therefor you will have a hard time to find a best algorithm.
I would imagine that finding a (axis align) navigation mesh could be expanded to 3d, so this sounds like a start for me, nevertheless, it sounds not like a trivial problem.
Author
it sounds not like a trivial problem.
exactly.
any other ideas? )
may be anyone has sample of https://mediatech.aalto.fi/~ari/Projects/OSPS/ ?
exactly.
any other ideas? )
No need to get snippy 
it sounds not like a trivial problem.
Means, that you will most likely not find a prepared, ready to use solution. You need to find an approximation, most likely you take an existing solution and try to tailor it to your problem.
you have a np-hard problem here
Np-hard means, that you will not be able to find an alogrithm which generates an optimal solution in time. This is, even a super computer of the size of the earth would not be able to generate optimal solutions in several years for medium input data. If you encounter a np-hard problem, you need to check the requirements of your principal. Go, explain that you have encountered an np-hard problem and that you only can find an approximation of the optimal solution. At this time it would be a good idea to relax the requirements and add other requirements (overlapping AABBs allowed ? Min/max size of AABB ? Are AABB allowed to include vertices ? Min/max number of AABBs per Mesh ? ...)
a (axis align) navigation mesh could be expanded to 3d
Have you looked into this. The issues are similar and I think, that it would be really a good start (Find a navigation mesh in an enclosed environment).
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
