Jump to content
  • Advertisement
Sign in to follow this  
Meai

Unity Polygon convexity test: can't get it right

This topic is 3055 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

I looked at this topic and implemented a few ideas, but nothing ever covers every special case I get. I have a list of vertices in clockwise or anti clockwise order and need to know if they are convex. There are no duplicate vertices. I will post my own take on it, maybe it's just a simple error I can't find. Appreciate any help! http://www.gamedev.net/community/forums/topic.asp?topic_id=467104 I need this to work in 3d space, but I check beforehand in a different function if all the vertices lie in the same plane. This means my vertex list is essentially 2d. Now I still need to know which axis I can drop, so I loop for all axis values, calculate the difference and sum the difference up. The two axis which have the biggest sum, get taken for consideration. e.g: Vertex 1: x = 5; z = -5; y = 5; Vertex 2: x = 6; z = -5; y = 10; x-axis sum = abs(5-6) = 1 z-axis sum = abs(-5--5) = 0 y-axis sum = abs(5-10) = 5 I determine that x and y must be the dominant axis to form the polygon. This is how I try at the moment: (i left the parts out, where I determine the dominant axis, because the code would be too long. Here I always drop the y values. I essentially check if the sign of the dotproduct between two vectors pointing outwards from one vertex ever changes.
bool positive = false;
	for (int i = 0; i < points.size(); ++i)
	{
		vector3 A = points.at((i+1) % points.size()) - points.at(i);
		vector3 B = points.at((i+2) % points.size()) - points.at((i+1) % points.size());
		float dot_product;

			float temp_ax = A.x;
			A.x = -A.z;
			A.z = temp_ax;
			A.y = 0;
			B.y = 0;
			dot_product = A * B;
		
		if (i == 0 && dot_product > 0)
		{
			positive = true;
		}
		if (i == 0 && dot_product <= 0)
		{
			positive = false;
		}
		if (dot_product > 0 && !positive) return false;
		if (dot_product <= 0 &&   positive) return false;
	}
	return true;

The next thing I'm gonna try, is this: http://demonstrations.wolfram.com/AnEfficientTestForAPointToBeInAConvexPolygon/ I was a bit reluctant to use this method, because I usually make mistakes implementing mathematical texts, since I'm not a native english speaker.

Share this post


Link to post
Share on other sites
Advertisement
You should probably be using crossproduct in 2d instead.

Assume polygone is checked in x-y plane and p is circular array of size N:


for n in 1..N
if sign(cross(p[n].xy, p[n+1].xy).z) != sign(cross(p[n].xy, p[n+2].xy).z)
return false
return true;


Share this post


Link to post
Share on other sites
Alright, took me a while to do, first time I did something in illustrator; but the following picture shows some things you can use to determine convexity:

Triangle convexity

So, you'd iterate over all vertices, and determine the direction (length not necessary, so just the sign is enough) of the cross-product between the 2 line-segments from the next and previous vertices to your current vertex. These signs should be equal for all vertices (either positive or negative).

Then the special case is when all angles ARE inward, but the total angles added are N * 360 degree, with N > 1 (ie. is goes 'round' twice or more, and thus overlap itself). Where ultimately the angle in total, as described in the picture, is (round-a-bout, take care with float in-precision) 360 degree.

I'm not aware if this is the most efficient method.

Share this post


Link to post
Share on other sites
Do you mean, that just the neighbouring line segments have to have the same sign in z, or do they all have to have the same. Because mzeo77 describes it so, that only neighbouring z signs have to be equal. But overall, there could be any number of change in signs.

This doesn't work either:


vector3 signs(0,0,0);
for (int i = 0; i < points.size(); ++i)
{
vector3 A = points.at((i+1) % points.size()) - points.at(i);
vector3 B = points.at((i+2) % points.size()) - points.at((i+1) % points.size());

vector3 tempsigns = Navigation::CrossProduct(A,B).normalize();
if (i == 0)
{
signs = Navigation::CrossProduct(A,B);
signs = signs.normalize();
}
if (signs.x != tempsigns.x || signs.y != tempsigns.y || signs.z != tempsigns.z)
{
return false;
}

}
return true;



@Decrius:
This means, even though the cross product test fails, I have to test further everytime and add up all angles? If they are exactly 360 or a multiple of it, then the test succeeds anyway, correct?

Share this post


Link to post
Share on other sites
Quote:
Original post by Meai
This means, even though the cross product test fails, I have to test further everytime and add up all angles? If they are exactly 360 or a multiple of it, then the test succeeds anyway, correct?


Almost. All cross-products must have the same sign! If one has a positive cross-product, it means that the angle as in the picture is to the left (or right, but lets say left) from the "current" line segment. It "turns" a number of degree's to the left.
If it is negative, it turns to the other side. So the next line-segment would not turn some degree to the left, but to the right when viewed from the "current" line-segment.
If you have 2 different cross-products, this means it is not convex! Get some paper and draw some cases. What if one segment points to the left after the previous, and the next to the right? Can it ever be convex?

So, first test if all cross-products have the same sign. If not, break out (this can be an early breakout) and return false for not being convex. if all cross-products have equal signs, you can iterate again (or have done this in the cross-product-calculating loop) and make sure the angles added are not larger then 2*PI (or larger then 3*PI, since radians added will only ever yield N*2*PI, and you have to be aware of floating point in-precision).

By angles I mean the angles shown in my picture, not the angles _within_ the polygon.

Share this post


Link to post
Share on other sites
When I came up with such a function myself, I came up with a simple method. You don't need to discard one axis for it either.

All I do is that for every line segment, detect if all other points in the polygon lie on the same side of that segment. If there is any line segment with points from the polygon that lie on either side, then it's concave.
To determine if points are on the same side or not, you can use dot products to calcluate the perpendicular component of the vector of each vertex from one of the points in the line segment, and then take the dot product of two of these. If it's negative, then they are on opposite sides.

This method also detects self-intersecting polygons where the total angles add up to 720 etc as not being convex. With a careful selection of points to use for sided-ness testing, this method can be O(n).

Share this post


Link to post
Share on other sites
Quote:
Original post by iMalc
With a careful selection of points to use for sided-ness testing, this method can be O(n).


How do you want to make a careful selection? If done the naive way this is O(n^2).
The method I described is neither optimal I guess, but it does only 1 dot and 1 cross product per vertex, so it is O(n) without any careful selection.

Share this post


Link to post
Share on other sites
@Decrius:
In your picture, you divided the dot product by "c" and "a", shouldn't that read that "c" and "b"?
Quote:
Then the special case is when all angles ARE inward

What is an inward angle? Angles < 90?

Quote:

and make sure the angles added are not larger then 2*PI (or larger then 3*PI, since radians added will only ever yield N*2*PI

So if the angle is larger than 2*PI, the polygon is not convex? I'm not following why we would need the whole thing with the angles.
A cross product between 2 vectors only ever returns a positive number, if the angle between the vectors forming the cross product is < 180, right?


Well I'll keep trying, but currently I don't have any success. Here is my take on iMalc's idea:
@iMalc: I didn't understand this part fully:
Quote:

To determine if points are on the same side or not, you can use dot products to calcluate the perpendicular component of the vector of each vertex from one of the points in the line segment, and then take the dot product of two of these. If it's negative, then they are on opposite sides.

but I took the idea, and implemented it a way I could think of:

for (int i = 0; i < points.size(); ++i)
{
vector3 lineSegment = points.at((i+1)%points.size()) - points.at(i);
for (int j = 0; j < points.size(); ++j)
{
// finding the normal to the line segment
float distanceToClosest = lineSegment * (points.at(j) - points.at(i));
vector3 closestPoint = points.at(i) + (distanceToClosest * lineSegment.normalize());
vector3 lineSegmentNormal = points.at(j) - closestPoint;
// the line segment normal * the vector from one of the line segment points (=closestPoint) to the point we currently test must be > 0
float result = lineSegmentNormal * (points.at(j) - closestPoint);
if (result < 0.0f)
{
return false;
}
}

}
return true;



But that isn't working in all cases either! If this code is correct, maybe my vertices just arent always in the same order. Very unlikely, but heck, I'd believe in anything right now.

Share this post


Link to post
Share on other sites
Quote:
Original post by Meai
In your picture, you divided the dot product by "c" and "a", shouldn't that read that "c" and "b"?


No, c and a. In the picture A-C means a to the right pointing vector of length |c| starting in C (|c| = |A - C| = sqrt((A.x - C.x)^2 + (A.y - C.y)^2 + (A.z - C.z)^2)). B-A is a to the top-left pointing vector starting in A. So, around vertex A we have a vector pointing from the previous vertex (C) to the current vertex (A), and a vector pointing from the current vertex (A) to the next vertex (B).

Quote:
Original post by Meai
What is an inward angle? Angles < 90?


Sorry, that was vague. With inward I meant an angle that makes the next line-segment turn to the same direction as all other line-segments seen from the previous line-segment.

Imagine we traverse the contour of the polygon with a car in positive (counter-clockwise) direction. We start at vertex A, we go to B. At B we need to turn an angle 'beta' to the left. Riding on we come to C, then again we need to turn left, with angle 'gamma', at A with angle 'alpha' and we're back at the begin position.

We keep going left. If we'd go right at one vertex, it means the polygon is concave aka. not convex! With the car, we keep going "inward", sorry somehow that word feels natural... ;)

Quote:
Original post by Meai
So if the angle is larger than 2*PI, the polygon is not convex? I'm not following why we would need the whole thing with the angles.
A cross product between 2 vectors only ever returns a positive number, if the angle between the vectors forming the cross product is < 180, right?


No, the cross-product can also give negative numbers. Namely: (I x J) = -(J x I) (think about this!). It doesn't matter thus what order we apply the cross-product, as long as we're consistent throughout the algorithm. We only need to know if they are equal in sign.

If the angle between 2 vectors is 0 or 180 degree, the cross-product is zero.

In the car example above, the car turned exactly 360 degree (to the left). However, if we only check, we can allow contours like below, because all cross-products have the same sign!

Star

In this case, the angles added are 720 degree = 4 * PI; so the polygon is not convex!

Share this post


Link to post
Share on other sites
Thank you Decrius, it's pretty clear now. Tomorrow I have to study for an unrelated test, but then I'll implement it...and probably find something to ask you again :)

btw: fancy graphics!

Share this post


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

  • Advertisement
  • Advertisement
  • Popular Tags

  • Similar Content

    • By RoKabium Games
      Been a bit quiet recently, but we've been busy bug fixing and tweaking things... Now we have lots more 'Particle effects' in the game, specifically here the Flamethrower and Enemy attacks!
    • By Alexander_Vovk
      Hello Guys!
      Please share your experience, where is it better to find sales manager  specialists for indie team of 6 + people(remotely)?
      Maybe someone has a good experience of cooperation with finding projects through sale managers(USA and Canada)?
        
      In our team more than 6 developers. We are working since 2014 now we are looking for projects mainly on upWork and Unity Connect.
      But that's not enough 
      This is the site of our team https://www.sixteensq.com/             
                                                 https://www.behance.net/Dezignw136f
      Thank you
      Best Regards
      Alex Vovk
      Co-Founder of Sixteen Squares
      Alexander_Vovk@outlook.com
       
    • By JoshuaFraser
      Hi and thanks for reading, I have an issue with this reactive crosshair script, everything works fine until I start changing the offset. Give the script a go and you will see what I mean, when I do SetOffset(0f); it doesnt always set back to the origional state, if anyone can spot a fix I'd be super appreciative!
      using System.Collections; using System.Collections.Generic; using UnityEngine; public class ReactiveCrosshair : MonoBehaviour { [SerializeField] GameObject c_limb_prefab; private float center_offset = 0f; private float current_offset = 0f; private float max_offset = .5f; private int number_of_limbs = 4; private float limb_length = .05f; private float limb_width = .005f; private List<GameObject> c_limbs = new List<GameObject>(); public void SetupCrosshair(){ for (int i = 0; i < number_of_limbs; i++) { GameObject line_go = (GameObject)Instantiate (c_limb_prefab); line_go.transform.SetParent (this.transform); Vector3 limb_pos = new Vector3 (0f,0f,0f); //line_go.transform.position = limb_pos; line_go.transform.localPosition = limb_pos; LineRenderer line = line_go.GetComponent<LineRenderer>(); line.startWidth = limb_width; line.positionCount = 2; line.SetPosition (0, line_go.transform.localPosition + new Vector3(center_offset, 0f, 0f)); line.SetPosition (1, line_go.transform.localPosition + new Vector3(center_offset + limb_length, 0f, 0f)); line.useWorldSpace = false; c_limbs.Add(line_go.gameObject); } if (c_limbs != null) { OrientLimbs (); SetOffset (0f); } } public void OrientLimbs(){ for (int i = 0; i < c_limbs.Count; i++) { float rotation_step = 360f / (float)c_limbs.Count; c_limbs [i].transform.RotateAround (c_limbs[i].transform.position, c_limbs[i].transform.forward, 90f + (rotation_step * (float)i)); } } public void SetOffset(float _current_spread){ float offset = Mathf.Lerp (0f, max_offset, _current_spread); for (int i = 0; i < number_of_limbs; i++) { if (offset > current_offset) { Vector3 pos = c_limbs [i].transform.position + (c_limbs [i].transform.TransformDirection (Vector3.right) * offset); c_limbs [i].transform.position = pos; } if (offset < current_offset) { Vector3 pos = c_limbs [i].transform.position - (c_limbs [i].transform.TransformDirection (Vector3.right) * offset); c_limbs [i].transform.position = pos; } } Debug.Log ("SetOffset() offset: " + offset.ToString () + " _current_spread: " + _current_spread.ToString() + " localPos: " + c_limbs[1].transform.localPosition); current_offset = offset; } }  
    • By Erik Nivala
      So, as the title says i am trying to figure out a good way sync all that information with other players in Unity. My problem is that i can't come up with a good solution since i am used to creating classes for everything e.g. attachments are its own class and then the weapon would save a reference to that attachment. But since you can't send custom classes over [Command] & [ClientRPC] i am a little stuck. A solution for this would be giving each attachment for a slot a unique ID and then passing the ID to other player but i feel like that is very error prone if other ppl add a new attachment or the IDs get mixed up.
      Is there a "standard" way that this is usually done that i am missing?
      I am fairly new to programming so any help is appreciated!
    • By MintyLyton
      I'm looking for any team / people that need a programmer for their project. I'm looking to expand my portfolio which you can see Here. I'm more experienced with Unity but I can spend the time to learn new Engines if that's your preference. I have worked on Unreal Engine 4 before but I might take some time to re-learn it, if the project requires it. Feel free to DM here or use the contact info on my website. 
    • By ethancodes
      I'm working on a system for my game that will allow the player to stack pick ups in a queue. As one pick up expires, the next automatically activates. I'm having an issue though where if I pick up the first one, it activates fine, but if i pick up a second directly after it, it overrides the first one, activates the second one, and then once it has run it's course, everything goes back to normal gameplay, no first pick up. I'm not sure why this is happening. Hopefully someone can spot what I'm doing wrong in my code.
      Here is the code for the pick up manager:
      // Update is called once per frame void Update () { if (pickUpQueue.Count != 0 && !pickUpActive) { pickUpActive = true; pickUpQueue[0].ActivatePickUp(); } DeactivatePickUp(); } void DeactivatePickUp () { if (pickUpQueue.Count != 0 && pickUpActive) { Destroy (pickUpQueue [0]); pickUpQueue.RemoveAt (0); pickUpActive = false; } } And here is the PickUp:
      public override void ActivatePickUp () { ball.GetComponent<Ball>().Speed = 2.0f; //increase ball speed... ball.GetComponent<Ball>().StartCoroutine(timer); //...set time that power up is active }  
      There is also a Base Pick Up:
      public void OnCollisionEnter2D (Collision2D collision) { Vector2 tweak = new Vector2 (Random.Range(0f, 0.2f),Random.Range(0f, 0.2f)); this.gameObject.GetComponent<Rigidbody2D>().velocity += tweak; //if the pickup makes contact with the paddle or ball.... if (collision.gameObject.tag == "Paddle" || collision.gameObject.tag == "Ball") { GameObject.FindObjectOfType<GameManager>().GetComponent<PickUpManager>().pickUpQueue.Add(this); Destroy(gameObject); //...and finally destroy power up object } } As a side note, I am trying to find a solution to this that will work for all of my pickups. Some pickups are ammo based, some are timed. 
    • By D34DPOOL
      Edit Your Profile D34DPOOL 0 Threads 0 Updates 0 Messages Network Mod DB GameFront Sign Out Add jobEdit jobDeleteC# Programmer for a Unity FPS at Anywhere   Programmers located Anywhere.
      Posted by D34DPOOL on May 20th, 2018
      Hello, my name is Mason, and I've been working on a Quake style arena shooter about destroying boxes on and off for about a year now. I have a proof of concept with all of the basic features, but as an artist with little programming skill I've reached the end of my abilities as a programmer haha. I need someone to help fix bugs, optomize code, and to implent new features into the game. As a programmer you will have creative freedom to suggest new features and modes to add into the game if you choose to, I'm usually very open to suggestions :).
      What is required:
      Skill using C#
      Experience with Unity
      Experience using UNET (since it is a multiplayer game), or the effort and ability to learn it
      Compensation:
      Since the game currently has no funding, we can split whatever revenue the game makes in the future. However if you would perfer I can create 2D and/or 3D assets for whatever you need in return for your time and work.
      It's a very open and chill enviornment, where you'll have relative creative freedom. I hope you are interested in joining the team, and have a good day!
       
      To apply email me at mangemason@yahoo.com
    • By davejones
      Is there a way to automatically change the start position of an animation? I have a bunch of animations set up on 3D models in unity. The issue is that I need to move the 3D models, however when I do so the animation start positions are not updated and I have to do it manually.

      Changing the transform of key frames is time consuming with the amount of animations I have, so I was wondering if there was a way to do it automatically?
    • By MoreLion
      hey all! We are looking for members for our Unity horror game! 
      Here’s the story:
      After a deadly virus plunges the world into chaos killing 85% of the human population there are now what they call “zones” these zones are watched very closely by the surviving government, people are checked every day for the virus, even if you touch the spit or any human waste or fluids of the victim who is infected, you will die. But one day, people in the west zone start to go missing, 1 woman goes outside the walls to uncover the mystery, is there more to the virus than meets the eye?, That is where your story starts.
      This game is not a long development game, I have loads other game ideas,
      I will also allow you to have a bit of creative freedom if you wish to add or share a idea!
      And no, it’s not a zombie game lol I feel like zombie games are too generic, in this game you will encounter terrifying beasts!
      There is some concept art one of our concept artists have made
      If interested email liondude12@gmail.com
    • By Canadian Map Makers
      GOVERNOR is a modernized version of the highly popular series of “Caesar” games. Our small team has already developed maps, written specifications, acquired music and performed the historical research needed to create a good base for the programming part of the project.

      Our ultimate goal is to create a world class multi-level strategic city building game, but to start with we would like to create some of the simpler modules to demonstrate proof of concept and graphical elegance.

       

      We would like programmers and graphical artists to come onboard to (initially) create:

      A module where Province wide infrastructure can be built on an interactive 3D map of one of the ancient Roman Provinces.
      A module where city infrastructure can be built on a real 3D interactive landscape.
      For both parts, geographically and historically accurate base maps will be prepared by our team cartographer. Graphics development will be using Blender. The game engine will be Unity.

       

      More information, and examples of the work carried out so far can be found at http://playgovernor.com/ (most of the interesting content is under the Encyclopedia tab).

       

      This project represents a good opportunity for upcoming programmers and 3D modeling artists to develop something for their portfolios in a relatively short time span, working closely with one of Canada’s leading cartographers. There is also the possibility of being involved in this project to the point of a finished game and commercial success! Above all, this is a fun project to work on.

       

      Best regards,

      Steve Chapman (Canadian Map Makers)

       
  • Advertisement
  • Popular Now

  • Forum Statistics

    • Total Topics
      631383
    • Total Posts
      2999689
×

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!