# Using infinitesimal offsets to avoid mesh special cases

This topic is 1504 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

A blog post about a technique I used at PathEngine to eliminate mesh special cases, for stuff like mesh traversals:

http://upcoder.com/10/infinitesimal-offset-meshes/

PathEngine does something a bit different from traditional nav mesh pathfinding, because we do stuff like projecting obstacles on to the ground, and actually generate a corresponding set of motion space boundaries on top of our 'ground meshes'.

The infinitesimal offsets technique described in that post has been particularly important for us in making this all work properly, but I think the technique can also be applied usefully to more direct nav mesh pathfinding situations..

Feedback appreciated!

Thomas

##### Share on other sites

We've moved the vertex off of vertical grid lines, and sloping lines which don't cross the intersection exactly will always have some finite offset from this intersection, and can't cross the vertex either.

How does that work? Are there special constraints on those sloping lines or something - are the points on the lines always represented with integer (grid) coordinates, while the vertexes are represented as floats?

Never mind:

Note that the mesh is still on an integer grid (not drawn), but with this grid slightly offset from the 'normal' grid.

Edited by tonemgub

##### Share on other sites

I am sceptical when you say "Most of the time points won't fall exactly on edges or vertices, and most of the time lines will just cross edges."

Because you can face design requirements where  'most of the time' points fall exactly on vertices and lines cross exactly vertices.

##### Share on other sites

I am sceptical when you say "Most of the time points won't fall exactly on edges or vertices, and most of the time lines will just cross edges."

Because you can face design requirements where  'most of the time' points fall exactly on vertices and lines cross exactly vertices.

Sure, there *can* be situations where you get a lot of these special cases.

But I'm really just talking about motivation there, and the possibility for such situations doesn't change the point of the article, I think.

Note that, even in situations with *lots* of vertex crossing, you can still apply the technique and end up with simplified traversal code.

##### Share on other sites

Then I worry after offset process when you say "Un-offset lines can't cross offset vertices".

Because purely mathematically speaking, for any vertice v in the offset domain, you can always find 2 points p1 and p2 in the un-offset domain such that the line (p1, p2) cross exactly v.

##### Share on other sites

Then I worry after offset process when you say "Un-offset lines can't cross offset vertices".

Because purely mathematically speaking, for any vertice v in the offset domain, you can always find 2 points p1 and p2 in the un-offset domain such that the line (p1, p2) cross exactly v.

Not so.

Remember that the un-offset points (from which you must choose p1 and p2) are on a discrete grid, and also (importantly) have a restricted range.

Try choosing some pair of points p1 and p2 to construct a small but non-zero offset from that grid intersection.

The range limit on these points means that you end up with a fixed range of integers to work with, and can therefore only construct a *finite* offset.

##### Share on other sites

Can you give me the units of your discrete domain (for un-offset points) and the range of min/max legal values ?

##### Share on other sites

Can you give me the units of your discrete domain (for un-offset points) and the range of min/max legal values ?

Doesn't actually matter, as long as it's a finite range. :D

But you can find this information, in the case of PathEngine, here:

http://pathengine.com/Contents/ProgrammersGuide/WorldRepresentation/PathEngineCoordinates/page.php

For info, the range supported for points in PathEngine is based on the need to apply expansion shape offsets, and mutliply up, for side tests and so on for *line intersections represented as fractions*.

##### Share on other sites

For my understanding, it is the interesting point.

I could trust you and think "oh yes he said that everything goes well, so stop asking questions now".

But no ;)

You have intricated values for units, range, iota1 and iota2. You look sure that the values you choosed in your engine avoid problems.

Do you have a proof ? Do you solve a system to find iota1 and iota2 from units and range ?

1. 1
Rutin
27
2. 2
3. 3
4. 4
5. 5

• 11
• 9
• 9
• 9
• 14
• ### Forum Statistics

• Total Topics
633312
• Total Posts
3011312
• ### Who's Online (See full list)

There are no registered users currently online

×