Segment selection between two points how to accurately select it

Recommended Posts

Posted (edited)

Hi

I have a setup of connected nodes via segments - these segments travel in any direction (think of like a connected road network).

My problem is how to accurately do collision checks for these segments and nodes.

Additionally some segments are curved via bezier curves which adds to the complexity of collision detection.

There are 2 types of issues i do not know how to solve:
1) User clicking with the mouse and detecting a node or a segment (for example adding a new road branching off an existing node or segment). Since adding a branch to a segment, would need to insert a new node and split the selected segment.

2) Detecting if a segment collides with another segment when trying to add a new one at run time.

My code setup is:

    public struct Node
{
public Vector3 Position { private set; get; }

//list of segments node is connected to
public Segment?[] Connections_Segments { private set; get; } //max 4 size

//list of nodes connected to - useful for pathfinder
public Node?[] Connections_Nodes { private set; get; } //max 4 size

//constructor etc etc
}

public struct Segment
{
public Node[] Nodes { private set; get; } //maximum of 2 nodes
public int Thickness { set; get; } //thickness of the road i.e 2 lane, 4 lane etc

public Vector3 AnchorPoint {private set; get; } //TODO bezier curve

//constructor etc etc
} 

Some things i thought about and tried but didn't work:

I added bounds to both nodes and segments, but soon realised this made no sense. In Unity bounds are axis aligned, this is no good for roads that do not follow along an axis (curved roads or roads going diagonally).

I also thought about using quad tree which only makes sense if the roads are straight, but they are obviously curved. And again using bounds is axis aligned so it won't be able to accurate represent roads that do not follow an axis (such as curved segments and diagonal segments).

So i am bit lost now what else to try. Hoping some one who has experience with design problems may have some suggestions that I can try.

Edited by thefollower

Share on other sites

Currently we are working on a similar project and use this technics you mentioned that are, known how to use, exactly what you need. Quad Trees are a must have for managing your node network because they make things faster regardless how your network is build, there are always nodes inside of quads so you now exactly what cloud of nodes is located where what helps finding all points and so there connections at a given area.

What we also do is defining a struct that contains all nodes belonging into the same connection path (like a lane on the street) when setting up our quad tree so every node knows to what connection it belongs and every connection knows the nodes that are inside the quad tree cell.

It is then easy to make an intersection test for a single segment that is defined by a start and end node, having a direction and an offset for the outer bounds to get if an object is overlapping this segment using its OBB (you need to code by yourself in Unity or use Collider.bounds)

Works also with splines because you will sample them anyways and while doing this have also a set of start/connection/end node segments

Share on other sites
Posted (edited)

The problem is using bounds is axis aligned. If the segment is not travelling along the axis' then the bounds is not accurate.

See image below:

So the middle one, which is what Unity does with bounding boxes is wrong for what i need. And thats the problem i am having.

So i cannot accurately detect when a mouse ray hits the segment, or when it collides with another segment because the bounds are not tightly wrapped around the segment shape, does that make sense?

How do i solve this problem, so it is more like the 3rd example in the image?

Edited by thefollower

Share on other sites
Posted (edited)

So i cannot accurately detect when a mouse ray hits the segment, or when it collides with another segment because the bounds are not tightly wrapped around the segment shape, does that make sense?

Yes, but it reduces the problem from N*N tests to a few interesting cases, and it's bloody fast.

If a single test doesn't seem feasible, find another way, for example, by splitting the problem. First try to eliminate all cases that are obviously non-overlapping, then for a few cases that might overlap, do a second test in some way. I find this the most rewarding part of programming, figuring out a way to solve a problem that looks impossible at first.

If you split the problem, for the first test, bounding box works nicely, it's fast enough for large quantities of areas, and it doesn't yield false negatives. It ends with a bunch of 2 particular shapes that might match. That problem is much simpler than matching zillions of shapes with each other. That's progress!! (If an idea doesn't solve the entire problem, don't discard it and stare yourself blind at its failure, it may be tweaked or used as building block in a larger context.)

Likely that second test depends on the shape of the two areas. If you have a lot of boxy shapes, you may want to make a dedicated test for that (your bounding box could be made to fit exactly if you exclude the triangles that are not covered). One other possible direction is to repeat the bounding box trick, but with several smaller boxes (several sub-boxes together make up the shape). You can perhaps try some line segment test too. Likely there is prior art in resolving collisions between exactly 2 shapes.

Edited by Alberth

Share on other sites

So i cannot accurately detect when a mouse ray hits the segment, or when it collides with another segment because the bounds are not tightly wrapped around the segment shape, does that make sense?

Yes, but it reduces the problem from N*N tests to a few interesting cases, and it's bloody fast.

If a single test doesn't seem feasible, find another way, for example, by splitting the problem. First try to eliminate all cases that are obviously non-overlapping, then for a few cases that might overlap, do a second test in some way. I find this the most rewarding part of programming, figuring out a way to solve a problem that looks impossible at first.

If you split the problem, for the first test, bounding box works nicely, it's fast enough for large quantities of areas, and it doesn't yield false negatives. It ends with a bunch of 2 particular shapes that might match. That problem is much simpler than matching zillions of shapes with each other. That's progress!! (If an idea doesn't solve the entire problem, don't discard it and stare yourself blind at its failure, it may be tweaked or used as building block in a larger context.)

Likely that second test depends on the shape of the two areas. If you have a lot of boxy shapes, you may want to make a dedicated test for that (your bounding box could be made to fit exactly if you exclude the triangles that are not covered). One other possible direction is to repeat the bounding box trick, but with several smaller boxes (several sub-boxes together make up the shape). You can perhaps try some line segment test too. Likely there is prior art in resolving collisions between exactly 2 shapes.

Well i can understand the quad tree is useful, but i am confused why unity bounds has to be axis aligned and not related to the rotation of the transform - it seems to be world space not local space which i find really strange. It doesn't seem like an easy calculation to check if the ray hits the two triangles outside the segment.  If i can get it like the second example in the previous image it would solve all the problems pretty easily.

Share on other sites

Well i can understand the quad tree is useful, but i am confused why unity bounds has to be axis aligned and not related to the rotation of the transform - it seems to be world space not local space which i find really strange.
axis-aligned is what makes it fast, so letting go of that basically kills the main advantage of the method.

However, there is no inherent reason why you have to use one coordinate system over another. That is, if local space works better, use that. As far as I know however local space is relative to each individual shape, wouldn't that make matching two different shapes complicated, to say the least?

You may want to wander into a neighbour thread, which looks related to me

https://www.gamedev.net/topic/689226-question-automated-minimal-bounding-box-decomposition/#entry5345164

Share on other sites

The problem is using bounds is axis aligned. If the segment is not travelling along the axis' then the bounds is not accurate. See image below: Q8GGgqC.png

It is regardless to the quad tree because if your segment is out of one quad it will stay in another that makes locating quads easier. I also wrote

get if an object is overlapping this segment using its OBB (you need to code by yourself in Unity or use Collider.bounds)

Where the keyword here is OBB (or OOBB, Object Oriented Bounding Box) that is easy to code and test against a segments line. Trust me, we have build a 1600km^2 GPS system covering our cars position in the game world

Share on other sites

The problem is using bounds is axis aligned. If the segment is not travelling along the axis' then the bounds is not accurate.

See image below:

So the middle one, which is what Unity does with bounding boxes is wrong for what i need. And thats the problem i am having.

So i cannot accurately detect when a mouse ray hits the segment, or when it collides with another segment because the bounds are not tightly wrapped around the segment shape, does that make sense?

How do i solve this problem, so it is more like the 3rd example in the image?

Unity's raycasting handles rotated boxes fine as far as I know, so why is detecting a mouse ray a problem? And for collision detection, what's wrong with Physics.OverlapBox? https://docs.unity3d.com/ScriptReference/Physics.OverlapBox.html

I might just not be understanding the problem correctly, but based on the image you posted it shouldn't be an issue in Unity.

Share on other sites

The problem is using bounds is axis aligned. If the segment is not travelling along the axis' then the bounds is not accurate.

See image below:

So the middle one, which is what Unity does with bounding boxes is wrong for what i need. And thats the problem i am having.

So i cannot accurately detect when a mouse ray hits the segment, or when it collides with another segment because the bounds are not tightly wrapped around the segment shape, does that make sense?

How do i solve this problem, so it is more like the 3rd example in the image?

Unity's raycasting handles rotated boxes fine as far as I know, so why is detecting a mouse ray a problem? And for collision detection, what's wrong with Physics.OverlapBox? https://docs.unity3d.com/ScriptReference/Physics.OverlapBox.html

I might just not be understanding the problem correctly, but based on the image you posted it shouldn't be an issue in Unity.

Well i am not using colliders and even if i do, 2D colliders are not rotated they are axis aligned so they would be like the second example in the image when i need the third example.

I just have a bounds type and a general ray casting method currently. If the object is rotated the bounds isn't accurate to the object as per the image i posted (the second one is where the issue lies) so i get issues. The hit point may be in the bounds but not in the actual segment. Hope that makes sense.

Since the objects are static on the x:z plane and non moving theres no point in 3D colliders or even 2D colliders, using the physics engine is wasted performance and my environment is pretty big it won't be feasible for me to use it.. I was hoping to make it more optimised by checking if the point hits the bounds but making sure the bounds was accurate to the segment (the third example in the image).

Share on other sites

Well i am not using colliders and even if i do, 2D colliders are not rotated they are axis aligned so they would be like the second example in the image when i need the third example.

I just have a bounds type and a general ray casting method currently. If the object is rotated the bounds isn't accurate to the object as per the image i posted (the second one is where the issue lies) so i get issues. The hit point may be in the bounds but not in the actual segment. Hope that makes sense.

Since the objects are static on the x:z plane and non moving theres no point in 3D colliders or even 2D colliders, using the physics engine is wasted performance and my environment is pretty big it won't be feasible for me to use it.. I was hoping to make it more optimised by checking if the point hits the bounds but making sure the bounds was accurate to the segment (the third example in the image).

The physics system is very efficient, especially if you user layer masks intelligently. The size of your environment shouldn't matter much. And the Physics2D library essentially mirrors its 3D counterpart, so you can just use Physics2D.OverlapBox.

If you're insistent on not using the physics system (I tend to avoid it but in the case of pure raycasting and intersection checks I find it's very useful), I guess you'll just have to write your own OBB logic

Share on other sites

Well i am not using colliders and even if i do, 2D colliders are not rotated they are axis aligned so they would be like the second example in the image when i need the third example.

I just have a bounds type and a general ray casting method currently. If the object is rotated the bounds isn't accurate to the object as per the image i posted (the second one is where the issue lies) so i get issues. The hit point may be in the bounds but not in the actual segment. Hope that makes sense.

Since the objects are static on the x:z plane and non moving theres no point in 3D colliders or even 2D colliders, using the physics engine is wasted performance and my environment is pretty big it won't be feasible for me to use it.. I was hoping to make it more optimised by checking if the point hits the bounds but making sure the bounds was accurate to the segment (the third example in the image).

The physics system is very efficient, especially if you user layer masks intelligently. The size of your environment shouldn't matter much. And the Physics2D library essentially mirrors its 3D counterpart, so you can just use Physics2D.OverlapBox.

If you're insistent on not using the physics system (I tend to avoid it but in the case of pure raycasting and intersection checks I find it's very useful), I guess you'll just have to write your own OBB logic

Yeah thats the best way to learn :) Plus even if i did use their system. It would be of no use for rotated objects anyway unless i use 3D colliders.

Share on other sites
Posted (edited)

Yeah thats the best way to learn :) Plus even if i did use their system. It would be of no use for rotated objects anyway unless i use 3D colliders.

Physics2D.OverlapBox has an angle parameter for rotation. But writing it from scratch for educational purposes is perfectly respectable imo.

Edited by cmac

Share on other sites

Yeah thats the best way to learn :) Plus even if i did use their system. It would be of no use for rotated objects anyway unless i use 3D colliders.

Physics2D.OverlapBox has an angle parameter for rotation. But writing it from scratch for educational purposes is perfectly respectable imo.

Would the angle parameter be for the box you are applying on top of existing colliders? The colliders would need to be rotated and then do a point overlap rather than a box for raycasting no?

Share on other sites
Posted (edited)

Yeah thats the best way to learn :) Plus even if i did use their system. It would be of no use for rotated objects anyway unless i use 3D colliders.

Physics2D.OverlapBox has an angle parameter for rotation. But writing it from scratch for educational purposes is perfectly respectable imo.

Would the angle parameter be for the box you are applying on top of existing colliders? The colliders would need to be rotated and then do a point overlap rather than a box for raycasting no?

Yes, the angle is for the imaginary box that overlaps the returned colliders. For normal 2D raycasts just use Physics2D.Raycast, but if you're talking about a mouse ray (or anything that uses the z-axis with 2D colliders), yes you'll need to use OverlapPoint (or just use 3D colliders and raycast along the correct axis, but that's less efficient).

IIRC, 2D colliders rotate around the z-axis corresponding to their transform by default, so you shouldn't need to worry about rotating them yourself.

Edited by cmac

Create an account

Register a new account

• Forum Statistics

• Total Topics
628357
• Total Posts
2982225

• 10
• 9
• 9
• 24
• 11