This post is completely off-topic regarding photography, still I know there are some 3D computing experts hanging here and which might be able to point me into the right direction…
At work I need to solve the following problem: I have a complex mathematical representation of a 3D surface, which is a single-valued function of the type
z = f(x,y)
Computing the function is computationally very expensive, therefore we want to pre-compute the function on a fine mesh and then interpolate the mesh to get the values.
The complication arises from the fact that the 3D surface is highly inhomogeneous, as it varies very rapidly in some regions while it is very smooth in some others. So, the mesh spacing should be locally adapted to the steepness of the surface. Moreover, the location of the steep regions in the (x,y) plane are a priori not precisely known.
Therefore, the surface should be sampled randomly, and the density of random points should be dynamically increased where the surface is steeper. Then, an mesh should be derived from the random points such that the interpolation accuracy is optimised.
Has anyone already encountered such a problem, or could put me in relation with knowledgeable people in the field? Is there any open-source code that performs at least some of the above steps?
Thanks a lot in advance, and sorry for spamming the forum with boring work issues…
If possible I’d not think of it as a mesh but as a point cloud. Using some spatial acceleration data structure (a quadtree should do), start at some level of the tree that matches the minimal number of samples you’d like to have in places of low variance, sample a bunch of (randomish) points per cell in the grid see if the variance is small enough if not, subdivide and recurse. You can then also use that same tree to accelerate the reconstruction of the surface. That sounds easy enough to be done from scratch, probably easier than ripping out the adaptive sampling code form say blender/cycles. It’s certainly not optimal, but possibly good enough.
There has been quite a bit of research on sampling techniques for ray/path tracing so if you can do without having a nice mesh, you can probably find a lot of inspiration there too.
I was also going to suggest a quadtree approach as well. I am generally familiar with interpolation methods, but typically only in relationship to “real” surfaces, such as landscapes. There is a module in the open source GRASS GIS suite called v.surf.rst that uses a quadtree sampling approach combined with regularized spline-tension interpolation, which offers very good “tuning” of the resulting surface. It is written in C, and you might get inspired from the source code?
Also check out some of the interpolation methods in meshlab. I think @Jonas_Wagner is probably correct that it may be better to envision your problem as a sampled point cloud, rather than a mesh or triangulated network.
Point clouds are often used for surface modeling in addition to true 3d objects. Many solutions to these problems come from LiDAR modeling methods. GRASS has many good tools for this, as does meshlab…
@HIRAM@Isaac researching a bit on the “Adaptive Mesh Refinement” technique, I found few libraries that seem to provide good interfaces: SAMRAI, libMesh and p4est.
Do you have any experience or knowledge about them?
These libraries look very interesting! I don’t have direct experience with them, nor, indeed, at the coding level with these types of tools. Most of my experience is in using these techniques at the software level. It seems like the right approach for your particular problem, though!
Just looking at the websites, it appears libMesh has some key features that I would have required of my geometry and physics tools: Tetrahedral meshing, and MPI support so I can run it on my super cluster. As for how they do AMR, I have no idea: but they do claim to do it or at least it’s stated as a major goal.
That’s about as much as I’m able to do.