Timeline for Minimum distance from point to surface
Current License: CC BY-SA 4.0
30 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| S Sep 17, 2022 at 22:45 | history | bounty ended | bubba | ||
| S Sep 17, 2022 at 22:45 | history | notice removed | bubba | ||
| Sep 14, 2022 at 2:32 | comment | added | EMP | You could mesh the volume, solve the eikonal equation or a p-poisson equation for the distance function, find the point with the smallest distance and then refine the mesh there and repeat. That would give you a method with provable error convergence properties. | |
| Sep 13, 2022 at 23:19 | answer | added | Marko Lalovic | timeline score: 6 | |
| Sep 11, 2022 at 23:11 | comment | added | bubba | @AmitHochman. Thanks. Meshing is a pretty good way to find approximate solutions. And then those solutions can be polished. But there are lots of details to worry about. For example, how good do the approximate solutions need to be to ensure that the polishing succeeds. And what’s the best way to do the polishing (which is really the crux of my question). | |
| Sep 11, 2022 at 16:56 | comment | added | lightxbulb | If you have a bound around the object (e.g. axis-aligned bounding box) then you can have the rays be shot in the direction of the box only. I suggest using a low-discrepnacy sequence for distributing the rays. Also you should distribute those uniformly over the solid angle subtended by the bounding box of your surface. | |
| Sep 11, 2022 at 16:54 | comment | added | lightxbulb | If you discretize your domain and compute the distance transform then you can start a walk from $p$ along the negative gradient of the distance field. In the worst case scenario you will end up choosing one of many possible equivalent minima on the discrete grid. The only error that you will have there would come from the discretisation of the domain. To speed this up you could have some adaptive structure on top in order to reduce the required resolution. Another option would be to shoot rays from $p$ in several directions and pick the intersection that is closest. | |
| Sep 11, 2022 at 14:47 | comment | added | Amit Hochman | If you want to find the distance from one surface to many points, you could approximate the surface with a 3D mesh, perhaps quite a coarse one and a finer one, and compute the nearest neighbors among the vertices. There are methods for doing this efficiently. The results could be refined in various ways, starting by finding the distance to the nearest polygon. | |
| Sep 10, 2022 at 22:27 | comment | added | bubba | @hardmath. Thanks. But the problem you mentioned is much simpler than mine, and can be solved algebraically. I’m interested in numerical methods that will work on a broader range of problems. | |
| Sep 10, 2022 at 22:23 | comment | added | bubba | @AmitHochman. Not necessarily. But we can assume that we have a software function that returns $F(x,y,z)$ at any input point $(x,y,z)$. And yes, I typically do want to calculate the distance from many points. | |
| Sep 10, 2022 at 19:14 | comment | added | hardmath♦ | Mathematical approaches to such problems have been kicked around at Math.SE, e.g. Minimum distance between a surface and a point. | |
| Sep 10, 2022 at 15:00 | history | tweeted | twitter.com/StackSciComp/status/1568615295190958081 | ||
| Sep 10, 2022 at 14:05 | comment | added | Amit Hochman | Is the function F(x) given with an analytical expression? Do you want to solve many points for one surface? | |
| S Sep 10, 2022 at 12:42 | history | bounty started | bubba | ||
| S Sep 10, 2022 at 12:42 | history | notice added | bubba | Draw attention | |
| Sep 10, 2022 at 2:12 | history | edited | bubba | CC BY-SA 4.0 |
added 60 characters in body
|
| Sep 10, 2022 at 1:59 | history | edited | bubba | CC BY-SA 4.0 |
added 121 characters in body
|
| Sep 10, 2022 at 1:46 | history | edited | bubba | CC BY-SA 4.0 |
Added examples of typical surfaces
|
| Sep 10, 2022 at 1:44 | comment | added | bubba | @hardmath. I added some example surface equations. | |
| Sep 9, 2022 at 13:38 | comment | added | hardmath♦ | The definition of $F(x)$ is missing. A typical difficulty, even for a smooth function, is distinguishing local minima from a global minimum. They would share a perpendicularity condition. | |
| Sep 9, 2022 at 3:09 | comment | added | Maxim Umansky | The approach with Grad(F) in general would have multiple solutions, so to find a true distance to the surface one would need to find all those solutions and compare them. But geometrically solving a problem like this would be convenient putting a sphere centered at the test point, and increasing the radius of the sphere gradually until it touches the surface. This approach can be probably used as the basis of an iterative solution algorithm here. | |
| Sep 9, 2022 at 0:28 | comment | added | bubba | I realize that the community bot isn’t going to tell me, but I really can’t imagine what’s unclear about my question. Happy to add more info if anyone can tell me what’s missing. | |
| Sep 9, 2022 at 0:27 | history | edited | bubba | CC BY-SA 4.0 |
added 75 characters in body
|
| Sep 9, 2022 at 0:23 | comment | added | bubba | @LutzLehmann. Yes, we can assume we have a surface. I have considered the equation-solving approach you suggested, but I’m wondering if a minimization approach might work better. | |
| Sep 9, 2022 at 0:21 | history | edited | bubba | CC BY-SA 4.0 |
added 75 characters in body
|
| Sep 8, 2022 at 22:00 | history | edited | bubba | CC BY-SA 4.0 |
added 203 characters in body
|
| Sep 8, 2022 at 16:49 | comment | added | CommunityBot | Please clarify your specific problem or provide additional details to highlight exactly what you need. As it's currently written, it's hard to tell exactly what you're asking. | |
| Sep 8, 2022 at 15:05 | comment | added | Lutz Lehmann | Is it guaranteed that $\{x:F(x)=0\}$ is a surface, that it has co-dimension $1$? Otherwise one can encode any system $\phi_(x)=0$ via sum-of-squares $F(x)=\sum\phi_i(x)^2$. If it is a surface, then at the optimum point the line to $r$ is orthogonal to the tangent plane, $F'(x)=\lambda (x-r)$, giving generically a full system, but will all critical points of the distance function as solutions. | |
| S Sep 8, 2022 at 11:33 | review | First questions | |||
| Sep 8, 2022 at 16:49 | |||||
| S Sep 8, 2022 at 11:33 | history | asked | bubba | CC BY-SA 4.0 |