[Algorithms] Nearest shapes to a point

Hi there

I'm delurking to ask a question for a friend of mine. He's trying to solve a 
problem which amounts to this:

There's a series of complex shapes (essentially long curving pipes which may 
twist, split, rejoin etc). The space may have five or six of these (or 
more), each a separate network but wound around each other in complex ways. 
He has a point in the space and he needs to know which network is nearest to 
the point. He can calculate anything about the space and the networks ahead 
of time, but the calculation itself is a real-time problem.

My feeling is that there are two main approaches that could work, but I'm 
obviously open to other suggestions.

Option 1: The networks are being given to him just as a bunch of models, but 
there's no reason in principle why he couldn't analyse them and convert them 
to a series of splines. One option would be to store these splines as a 
series of lists at a progressively greater level of detail, including some 
metric defining how good the detail is (how closely the spline matches the 
curve, eg a maximum distance from the real curve to the spline segment). 
Then he could take the point and calculate the nearest splines at each level 
of detail (taking into account the margin of error), gradually homing in 
until only one segment is selected. I can visualise this algorithm pretty 
well, but I don't know how efficient it would be, or how easy it would be to 
calculate the splines - especially since his client wants to be able to add 
new networks at a later date without additional coding.

Option 2: He could take the whole space and partition it in some way into 
regions such that each region belongs to a particular network, ie, for every 

Re: [Algorithms] Nearest shapes to a point

Danny,

I'm not sure I will be of tremendous help here, but I would be wary of 
converting a complex shape into another complex shape, unless it 
naturally solves your problem to do so.  The errors introduced first in 
the conversion process, then later in the distance functions, might be 
unwieldy and error-prone.

Trying to encode the nearest network index--an intersection of the all 
the individual networks as a function of spatial coordinates--can be a 
very noisy function if they are close together and bending a lot.  But 
encoding each one separately could be quite cheap, depending on how it's 
done.

It sounds like what your friend might look into some derivative of a 
level-set data structure, where space is mapped to a distance function 
for each individual network.  Then, by querying the level-set for each, 
sampling the space for the distance to the surface, he can find the 
smallest distance and thus the nearest network.  In truth, I have never 
implemented such a thing nor do I have any clear concept of the 
constraints or feasibility of the runtime approaches--you didn't really 
specify a budget anyway.

Best of luck,
JH

Danny Kodicek wrote:
> Hi there
>
> I'm delurking to ask a question for a friend of mine. He's trying to solve a 

Re: [Algorithms] Nearest shapes to a point

 > I'm not sure I will be of tremendous help here, but I would 
> be wary of 
> converting a complex shape into another complex shape, unless it 
> naturally solves your problem to do so.  The errors 
> introduced first in 
> the conversion process, then later in the distance functions, 
> might be 
> unwieldy and error-prone.

Hmm. I see your point, although to some extent I guess it depends on how
unfriendly the curves involved are.

> 
> Trying to encode the nearest network index--an intersection 
> of the all 
> the individual networks as a function of spatial 
> coordinates--can be a 
> very noisy function if they are close together and bending a 
> lot.  But 
> encoding each one separately could be quite cheap, depending 
> on how it's 
> done.

Right. So what you're saying is that partitioning the space up might be more
expensive than just storing the individual distance metrics to each network.
I see your point.

> 
> It sounds like what your friend might look into some derivative of a 
> level-set data structure, where space is mapped to a distance 

Re: [Algorithms] Nearest shapes to a point

Danny Kodicek wrote:
> Option 2: He could take the whole space and partition it in some way into 
> regions such that each region belongs to a particular network, ie, for every 
> point in a particular region, the nearest network to that point is the same. 
> Once he's done that, it should be possible to break that partition up into 
> some kind of BSP tree or something of that sort. I suspect that both these 
> tasks are solvable by some standard algorithm, but I have no idea what that 
> algorithm is.
>   

The problem space is actually exactly a voronoi feature region (which 
you can think of as expanding voronoi point regions into extruded 
shapes). Unfortunately, if the features are 3D, then the separating 
planes become curved, and testing becomes expensive, but if you can 
forgo the thickness of the pipes themselves, then you can build a BSP or 
similar hierarchical structure out of the voronoi separating planes.

Sincerely,

jw

-------------------------------------------------------------------------
Sponsored by: SourceForge.net Community Choice Awards: VOTE NOW!
Studies have shown that voting for your favorite open source project,
along with a healthy diet, reduces your potential for chronic lameness
and boredom. Vote Now at http://www.sourceforge.net/community/cca08
_______________________________________________
GDAlgorithms-list mailing list
GDAlgorithms-list <at> lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list

Re: [Algorithms] Nearest shapes to a point

> Danny Kodicek wrote:
> > Option 2: He could take the whole space and partition it in 
> some way into 
> > regions such that each region belongs to a particular 
> network, ie, for every 
> > point in a particular region, the nearest network to that 
> point is the same. 
> > Once he's done that, it should be possible to break that 
> partition up into 
> > some kind of BSP tree or something of that sort. I suspect 
> that both these 
> > tasks are solvable by some standard algorithm, but I have 
> no idea what that 
> > algorithm is.
> >   
> 
> The problem space is actually exactly a voronoi feature region (which 
> you can think of as expanding voronoi point regions into extruded 
> shapes). Unfortunately, if the features are 3D, then the separating 
> planes become curved, and testing becomes expensive, but if you can 
> forgo the thickness of the pipes themselves, then you can 
> build a BSP or 
> similar hierarchical structure out of the voronoi separating planes.

Thank you! That's the word I was looking for, I remember reading about these
here a while back. I'll pass this on, although he was pretty happy with the
octree idea and I think he's going with that at the moment. (actually, the
octree idea is much the same thing, of course, just using a cubic
approximation to the same space)

[Algorithms] Shortest path between 2 points on a triangle mesh

-------------------------------------------------------------------------
Sponsored by: SourceForge.net Community Choice Awards: VOTE NOW!
Studies have shown that voting for your favorite open source project,
along with a healthy diet, reduces your potential for chronic lameness
and boredom. Vote Now at http://www.sourceforge.net/community/cca08

_______________________________________________
GDAlgorithms-list mailing list
GDAlgorithms-list <at> lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
Archives:
http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list

Re: [Algorithms] Shortest path between 2 points on a triangle mesh

-------------------------------------------------------------------------
Sponsored by: SourceForge.net Community Choice Awards: VOTE NOW!
Studies have shown that voting for your favorite open source project,
along with a healthy diet, reduces your potential for chronic lameness
and boredom. Vote Now at http://www.sourceforge.net/community/cca08

_______________________________________________
GDAlgorithms-list mailing list
GDAlgorithms-list <at> lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
Archives:
http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list

[Algorithms] Exactly mapping texels to pixels

Hi all,

I just finished getting a 1:1 mapping between texels and pixels working 
for some font rendering.  After getting through all the standard pixel 
center shifting bugs, UV mapping errors, and so forth, I eventually ran 
into a roadblock where everything was apparently fine, but still didn't 
work right.  After looking at the math, I noticed I was getting minor 
errors... very small, but present, when computing the texel based on the 
width and height of the texture.  Turns out I was using a 
non-power-of-two texture as the image, and the miniscule error (6 or 7 
significant digits with the FPU in double mode) was considerably worse 
on the GPU, or at least the same error but significant.

Seeing as how this requirement wasn't mentioned on two of the sites I 
went to when researching texel/pixel mapping, I thought I'd put out the 
question if it's possible to get a straight mapping with oddball texture 
sizes?  Some GPU's have an index mode that allows integer values to be 
used directly for UVs without scaling, I realize, but I'm more curious 
if it's just a quirk of floating point math.

In other words, is it true that, within limits of precision, scaling 
with powers of two are cleanly invertible: 
            x * p / p = x,     for all x which are floats, and p which 
are any exact power of two (positve or negative)

I think so, due to how fp numbers are represented and computed.  Any 
thoughts?

Thanks,
JH

-------------------------------------------------------------------------
Sponsored by: SourceForge.net Community Choice Awards: VOTE NOW!
Studies have shown that voting for your favorite open source project,
along with a healthy diet, reduces your potential for chronic lameness
and boredom. Vote Now at http://www.sourceforge.net/community/cca08
_______________________________________________
GDAlgorithms-list mailing list
GDAlgorithms-list <at> lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
Archives:
http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list

Re: [Algorithms] Exactly mapping texels to pixels

Jason Hughes wrote:
> went to when researching texel/pixel mapping, I thought I'd put out the 
> question if it's possible to get a straight mapping with oddball texture 
> sizes?  Some GPU's have an index mode that allows integer values to be 
>   

Yes, it is, but you have to be careful with precision. Computing first 
the size of a pixel, and then multiplying that value by the width of the 
texture is the wrong thing to do, for example. That being said, an error 
that is less than one-tenth of a pixel width across the entire texture 
shouldn't end up being visible if you're using NEAREST filter mode. If 
it is visible, you have some bigger problem.

> In other words, is it true that, within limits of precision, scaling 
> with powers of two are cleanly invertible: 
>             x * p / p = x,     for all x which are floats, and p which 
> are any exact power of two (positve or negative)
>   

Yes, that is true, within limits (you'll run out of exponent at some point).

Sincerely,

jw

-------------------------------------------------------------------------
Sponsored by: SourceForge.net Community Choice Awards: VOTE NOW!
Studies have shown that voting for your favorite open source project,
along with a healthy diet, reduces your potential for chronic lameness
and boredom. Vote Now at http://www.sourceforge.net/community/cca08
_______________________________________________
GDAlgorithms-list mailing list
GDAlgorithms-list <at> lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
Archives:
http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list

[Algorithms] Axis aligned bounding box of cylinder

-------------------------------------------------------------------------
Sponsored by: SourceForge.net Community Choice Awards: VOTE NOW!
Studies have shown that voting for your favorite open source project,
along with a healthy diet, reduces your potential for chronic lameness
and boredom. Vote Now at http://www.sourceforge.net/community/cca08

_______________________________________________
GDAlgorithms-list mailing list
GDAlgorithms-list <at> lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
Archives:
http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list