Jump to content
  • Advertisement
Sign in to follow this  
ThomasYoung

Using infinitesimal offsets to avoid mesh special cases

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

If you intended to correct an error in the post then please contact us.

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


Link to post
Share on other sites
Advertisement

 

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


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 ?

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!