2 Jul 23:17 2008

### [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
```

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

3 Jul 10:32 2008

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

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

3 Jul 23:15 2008

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

4 Jul 10:24 2008

### 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)
```

12 Jul 17:53 2008

### [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```
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```
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

```
14 Jul 09:02 2008

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

```
14 Jul 17:07 2008

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