Danny Kodicek | 2 Jul 23:17 2008
Picon

[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 
(Continue reading)

Jason Hughes | 3 Jul 07:18 2008

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 
(Continue reading)

Danny Kodicek | 3 Jul 10:32 2008
Picon

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 
(Continue reading)

Jon Watte | 3 Jul 23:15 2008
Picon

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
(Continue reading)

Danny Kodicek | 4 Jul 10:24 2008
Picon

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)
(Continue reading)

Willem Kokke | 12 Jul 17:53 2008
Picon

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

I'm trying to find the approximate shortest path between two points on a triangle mesh. The meshes consists of about 30 000 polys and 15.000 vertices.
It has to be reasonably fast

Currently I'm thinking about a simple A* search over the connectivity information (so I will get a path along the edges of the triangles), and then calculate a smooth(er) path across the triangle surface afterwards.
I'm fairly certain this will work, but i'm worried about the performace characteristics.

Can anybody think of a better approach, or better search terms?

Thanks,
Willem

-------------------------------------------------------------------------
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
Jason Hughes | 12 Jul 18:17 2008

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

You can look into recursive A*.  It works similarly to mesh simplification, where sections of the triangle mesh are collapsed and simplified to larger triangles.  You do A* on the low-res mesh first, then internally do A* on each LOD, given start and end vertices, then recurse until you're at the highest level of detail.

I'm not certain it's guaranteed to get the shortest path in absolute terms every time, as the simplification may not represent precisely the same connectivity costs, but it should be quite fast to get an initial good path direction, then work out the details as you cross those thresholds iteratively (rather than compute the whole path up front), which is particularly nice when your units may change their minds before consuming the whole path.

A* has pretty good performance, though the search space can be quite large and in situations where the estimate is not very close to the cost metric, it can be a somewhat poor guide for pathing.  Another possibility is geodesic pathing.  (Fast Exact and Approximate Geodesic Paths on Meshes (2004))  I haven't implemented these kinds of methods, nor looked into them to any great detail, but it produces the shortest path across faces using a triangular input mesh.  So no smoothing step needed.  There are other more recent papers on the subject... this one just one that I found immediately.

Let us know how it turns out,
JH

Willem Kokke wrote:
I'm trying to find the approximate shortest path between two points on a triangle mesh. The meshes consists of about 30 000 polys and 15.000 vertices.
It has to be reasonably fast

Currently I'm thinking about a simple A* search over the connectivity information (so I will get a path along the edges of the triangles), and then calculate a smooth(er) path across the triangle surface afterwards.
I'm fairly certain this will work, but i'm worried about the performace characteristics.

Can anybody think of a better approach, or better search terms?

Thanks,
Willem
-------------------------------------------------------------------------
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
Jason Hughes | 13 Jul 23:37 2008

[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

Jon Watte | 14 Jul 09:02 2008
Picon

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

Stefan Dänzer | 14 Jul 17:07 2008
Picon

[Algorithms] Axis aligned bounding box of cylinder

Hi folks,
I'm trying to find an Axis aligned bounding box (AABB) for a cylinder. The cylinder is given as a point in space, a vector (the direction of the center line), length and radius. I was wondering how one would compute an AABB for this representation.
Surprisingly, finding an Oriented bounding box (OBB) is a bit more simple than finding the AABB. One would just find a perpendicular vector to the vector on the center line, this would give another perpendicular vector by applying the cross product to these vecotrs. Scaling the two found perpendicular vectors by the radius of the cylinder would give the points on the middle of the edges of the OBB.

regards,

Stefan Dänzer

--
"Work like you don't need the money, love like you've never been hurt and dance like no one is watching." - Randall G Leighton

-------------------------------------------------------------------------
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

Gmane