I have many dots placed on the surface of a 3D sphere.
How can I compute the outline of the shape that encompass all the points at distance X of any of the dots ?
Here is an illustration to understand it better (in 2D for more clarity):
Every small red dot have their own "radius" property. If a point in the plane is inside the range "radius" of a red dot, it is represented in grey on the image. What I am looking for is a list of lines allowing me to draw as precisely as possible the outline of the shape.
I need it to be really fast because there may be tens of thousands of those red dots, so I can't do some brut-force stuff.
I already have a k-d Tree representation of these points if this may help (k = 2 because points are stored as lat long values ).
The animation above represents better what I need. You can see lots of blue "parts of spheres" of which I know the "centers" and the radiuses. And what I really need is the outline of this blue shape (there may be holes inside of it like in the first illustration)
CodePudding user response：
Well as you want correct output (no distortion) then I would go for ray caster and shaders... However not to get overwhelmed you by both C & GLSL at the same time I decided to do this in pure SW render (porting into GLSL is easy from that)...
It works like this:
loop through "all" pixels of screen
You can use expected BBOX of your sphere clipped by screen to improve speed...
cast a ray from camera focus into actual screen pixel
compute intersection between ray and sphere
You can use this:
As you can see no distortions are present...
In case you do not want to ray cast like this then you have to convert your points into triangulated polygons covering their radius and sphere curvature in Cartesian and render them like this:
- Render all circles with edge color
- Render all circles with inside color but with radius decreased by edge width
In case you do not want the inside its enough to have just the edges polygons instead and render once ...