Jump to content


Photo

2d Polygons


  • This topic is locked This topic is locked
22 replies to this topic

#1 cambesa

cambesa

    GMC Member

  • GMC Member
  • 868 posts
  • Version:Unknown

Posted 30 September 2007 - 06:49 PM

everybody knows how vertexes/polygons work in 3d.
2 3d points and a line between them.
i need that in 2d.

i need this for lighting and physics.
with that polygons, the fps will be much higher then when i check every pixel.
my mission is to make a coordinates list from a 2d image.
so check every outer pixels and make a line between those points.
and when the pixels are in a straight line i need one line insteed of multiple lines in a straight line.

i just need a ds list or map with coordinates of the outer vertexes of a 2d sprite.

somebody knows a way to make that?
it will be very usefull with creating 2d dynamic soft shadows and rigid body dynamics.
i was working on both in a while but im stuck at the polygons.

if somebody knows a script for creating a list with the coordinates of vertexes of a 2d sprite. please post it or help me making the script.
after i have that script ill make a script to rotate the coordinates in the list by using lengtdir_x and y.

thanks in advance.

Edited by cambesa, 30 September 2007 - 07:09 PM.

  • 0

Insanely large signature removed by a moderator.

(I've had that signature for decades but okay...)


#2 ragarnak

ragarnak

    GMC Member

  • GMC Elder
  • 19468 posts
  • Version:GM8

Posted 30 September 2007 - 07:15 PM

everybody knows how vertexes/polygons work in 3d.
2 3d points and a line between them.
i need that in 2d.

<{POST_SNAPBACK}>

I suggest you take a look in GM's Help, the "The Game Maker Language (GML)" -> "Game graphics" -> "Advanced drawing functions" chapter.

i just need a ds list or map with coordinates of the outer vertexes of a 2d sprite.

somebody knows a way to make that?

Maybe someone does.

But the question is : what did YOU do to find/make that list ?

First try it yourself and, if you get into a fix, show us what you did. I'm quite sure if you do that that most of us will be more-than-willing to help you iron-out any-and-all problems you might have with it.
  • 0

#3 GearGOD

GearGOD

    Deus Verus

  • GMC Member
  • 2153 posts

Posted 30 September 2007 - 07:40 PM

Hahah. Constructing a hull from a set of points is not a simple task. It's the subject of several research papers I read recently.

I am guessing no one is going to help you here beyond naiive approaches which have terrible flaws. So either don't even try, or go do some serious research and good luck to you.
  • 0
Engineers are not programmers. Stop thinking that you can save a few bucks by writing code yourself instead of hiring a programmer. Your code sucks.

#4 ragarnak

ragarnak

    GMC Member

  • GMC Elder
  • 19468 posts
  • Version:GM8

Posted 30 September 2007 - 08:05 PM

So either don't even try, or go do some serious research and good luck to you.

<{POST_SNAPBACK}>

Maybe you can put something constructive into this thread and tell us why its such a big problem ?

Maybe you have even read about a simple solution that might not be optimal but will do the job which you could tell us about ?

It would help the OP, and I would probably learn from it too. :D

P.s.
A quick Google with the words "hull polygon" shows several methods to convert a set of points into a convex polygon.

Edited by ragarnak, 30 September 2007 - 08:06 PM.

  • 0

#5 GearGOD

GearGOD

    Deus Verus

  • GMC Member
  • 2153 posts

Posted 30 September 2007 - 08:20 PM

Convex hulls are simple and have been implemented in GM. By myself included.

The problem is that they're too simple and aren't suitable for use in collision detection. I had a brief look and wasn't even able to find the research papers I saw so I can't offer much information. Naiive approaches involve scanning lines across the sprite and acting like a 3d laser scanner. It is obviously limited in that the lines can't penetrate inside the shape. It also gets really nasty if you try multi-bounce or something because the main requirement is not to collect the boundary points, but to order them.
  • 0
Engineers are not programmers. Stop thinking that you can save a few bucks by writing code yourself instead of hiring a programmer. Your code sucks.

#6 ragarnak

ragarnak

    GMC Member

  • GMC Elder
  • 19468 posts
  • Version:GM8

Posted 30 September 2007 - 08:28 PM

...  the main requirement is not to collect the boundary points, but to order them.

<{POST_SNAPBACK}>

I don't quite get it I'm afraid : At least one of the Googeled solutions had no problem with creating a hull around a "random" number of points. If that is the case than a "random" collection of all visible pixels of a sprite should, although maybe slow(er than using only the pixels forming the sprites boundary), result in such a hull too.
  • 0

#7 GearGOD

GearGOD

    Deus Verus

  • GMC Member
  • 2153 posts

Posted 30 September 2007 - 08:31 PM

Could you paste the links? This is actually something I need to solve in the near time.

But basically, simply identifying boundary points is easy. We have edge detection filters for that. The trouble is that in order to construct a useful polygon, the boundary points must be ordered. Either clock or anti-clock wise. If they're not ordered, they are meaningless.
  • 0
Engineers are not programmers. Stop thinking that you can save a few bucks by writing code yourself instead of hiring a programmer. Your code sucks.

#8 ragarnak

ragarnak

    GMC Member

  • GMC Elder
  • 19468 posts
  • Version:GM8

Posted 30 September 2007 - 08:41 PM

Could you paste the links? This is actually something I need to solve in the near time.

<{POST_SNAPBACK}>

Ofcourse. It was the third result on that "hull polygon" search I did : http://www.nceas.ucs...onvexHullR.html

The trouble is that in order to construct a useful polygon, the boundary points must be ordered. Either clock or anti-clock wise. If they're not ordered, they are meaningless.

I understand that the resulting polygon must be either of those forms. But whats the problem with that ? For me it looks like picking (for instance) the bottom-left point, assume its "pointing" up, and than use a sort of "find your way outof the maze by keeping your left hand against the wall" problem : get the angle towards all of the other points, and take the one that is pointing the furthest towards the west of the current direction.
  • 0

#9 GearGOD

GearGOD

    Deus Verus

  • GMC Member
  • 2153 posts

Posted 30 September 2007 - 08:48 PM

For a convex hull yeah that's the case. But once again a convex hull is not sufficient for applications like collision detection (which is what I'm doing for example).

For a hull that's actually useful in such applications, we're looking at much more complicated approaches such as this.
  • 0
Engineers are not programmers. Stop thinking that you can save a few bucks by writing code yourself instead of hiring a programmer. Your code sucks.

#10 ragarnak

ragarnak

    GMC Member

  • GMC Elder
  • 19468 posts
  • Version:GM8

Posted 30 September 2007 - 09:07 PM

For a convex hull yeah that's the case. But once again a convex hull is not sufficient for applications like collision detection (which is what I'm doing for example).

<{POST_SNAPBACK}>

That I do not know anthing about I'm afraid (have never looked at it).

For a hull that's actually useful in such applications, we're looking at much more complicated approaches such as

I'm afraid I do understand what they are talking about there. The subject does not seem to return anywhere (in the description or otherwise), and neither do they seem to be talking about a "hull" (which is, by definition, convex). :D
  • 0

#11 GearGOD

GearGOD

    Deus Verus

  • GMC Member
  • 2153 posts

Posted 30 September 2007 - 09:19 PM

Yeah that's just a description of one of the papers I saw. I wasn't actually able to find it now.
Basically this is our problem:
Posted Image
On the left is the convex hull, on the right is the concave.
As you can see the convex can be calculated very intuitively, but would be useless in representing the area occupied by our sprite for something like collisions.

Edit: by the way, for a shape as simple as this, naiive approaches like tracing rays from a few angles will work just fine.

Edited by GearGOD, 30 September 2007 - 09:20 PM.

  • 0
Engineers are not programmers. Stop thinking that you can save a few bucks by writing code yourself instead of hiring a programmer. Your code sucks.

#12 ragarnak

ragarnak

    GMC Member

  • GMC Elder
  • 19468 posts
  • Version:GM8

Posted 30 September 2007 - 09:46 PM

As you can see the convex can be calculated very intuitively, but would be useless in representing the area occupied by our sprite for something like collisions.

<{POST_SNAPBACK}>

From my POV the hull for that popsickle on the right looks like its the same as the outline of it. Do you know of a case in which that would not happen ?

P.s.
I'm going to hit the sack soon, its rather late over here.
  • 0

#13 GearGOD

GearGOD

    Deus Verus

  • GMC Member
  • 2153 posts

Posted 30 September 2007 - 09:50 PM

You're coming back to the original point. We can identify the outline, but obtaining a meaningful list of points along it is a different story. I can't tell you how to do it, I don't know. It's something I'll be researching after exams.
  • 0
Engineers are not programmers. Stop thinking that you can save a few bucks by writing code yourself instead of hiring a programmer. Your code sucks.

#14 ragarnak

ragarnak

    GMC Member

  • GMC Elder
  • 19468 posts
  • Version:GM8

Posted 30 September 2007 - 10:03 PM

You're coming back to the original point. We can identify the outline, but obtaining a meaningful list of points along it is a different story.

<{POST_SNAPBACK}>

Hmmm ... That could be why the OP removed his "hull" reference from his origional question. Because he did not want the convex one, but one hugging the shape.

I can't tell you how to do it, I don't know. It's something I'll be researching after exams.

I'm sure the OP will be gratefull for what you can tell him about it. :D
  • 0

#15 EricDB

EricDB

    Eric Burgess

  • GMC Elder
  • 920 posts
  • Version:GM8

Posted 01 October 2007 - 07:30 PM

A first approximation to the solution, and one that I think would work in most cases, would be this:
  • Assume you have the set of outline pixels, by whatever method.
  • Pick any pixel in your outline set, and call it your "current pixel".
  • Add the "current pixel" to your ordered list, and remove it from the outline set.
  • Check the adjacent coordinates to find one that's also in the outline set. If you found one, make that your "current pixel" and go back to step 3. Otherwise, you're done.
Of course, this method requires that you have a good method of identifying outline pixels, and that your sprite is connected (no little separate bits). A "good method" is one which identifies all the outline pixels, and nothing extra, so that any outline pixel has exactly two neighboring outline pixels.

Assuming those things, this method should get you an ordered list of outline pixels. You might have to flip your list to get it in the proper CW/CCW orientation...detecting whether that's necessary is another interesting problem, but should be doable (you could add the angles from each pixel to its next pixel, all the way around, and should end up with + or - 360 degrees).
  • 0

#16 cambesa

cambesa

    GMC Member

  • GMC Member
  • 868 posts
  • Version:Unknown

Posted 01 October 2007 - 09:17 PM

now i know i need the concave.
and no problems with colision detection, i want to save 2 points and then do collision_line.
not just 2 points but 2 points per line.

when i know how to make a list of those points i can make rigid body dynamics and dynamic soft shadows in one engine, and thats what i need for my games.

thanks for help, ill still do research about concave.

edit: now the question is... how to get the outline pixels, make a concave of it and put it in a list?
thanks for all your replys.

Edited by cambesa, 01 October 2007 - 09:30 PM.

  • 0

Insanely large signature removed by a moderator.

(I've had that signature for decades but okay...)


#17 GearGOD

GearGOD

    Deus Verus

  • GMC Member
  • 2153 posts

Posted 02 October 2007 - 06:29 AM

EricDB: That makes one hell of an assumption that the outline is perfect. If there's even a slight discontinuitiy, moving on to a random pixel will mean destroying the winding order.
I think its important to note that a field of points can have more than one concave solution.
  • 0
Engineers are not programmers. Stop thinking that you can save a few bucks by writing code yourself instead of hiring a programmer. Your code sucks.

#18 xot

xot

    GMC Dismember

  • GMC Elder
  • 4785 posts
  • Version:GM:Studio

Posted 02 October 2007 - 06:40 AM

Did you guys look at this?

http://ubicomp.algor...oncavehull.html

http://ubicomp.algor.../downloads.html


Otherwise, off the top of my head, I was thinking of something along the lines of a flood fill combined with a linked list.
  • 0
GMLscripts.com, rise from your grave!

If any of my posts contain broken images or links, I can probably supply them for you. PM with a link to the post.

#19 EricDB

EricDB

    Eric Burgess

  • GMC Elder
  • 920 posts
  • Version:GM8

Posted 02 October 2007 - 08:16 PM

EricDB: That makes one hell of an assumption that the outline is perfect. If there's even a slight discontinuitiy, moving on to a random pixel will mean destroying the winding order.
I think its important to note that a field of points can have more than one concave solution.

<{POST_SNAPBACK}>


A field of points may have more than one concave solution, but a GM sprite cannot, as far as I can see. I think a perfect outline (assuming a connected sprite) should be easy to get, though possibly not fast.

The way I see it, a pixel is in the outline set if and only if it has at least one transparent neighbor.

Is there a flaw with this method, other than speed?

Edit: I guess there's one more assumption--that the sprite is "thick enough"...one- or two-pixel thick areas could lead to adjacent outline pixels that should not actually be connected to each other.

Edited by EricDB, 02 October 2007 - 08:18 PM.

  • 0

#20 Yourself

Yourself

    The Ultimate Pronoun

  • GMC Elder
  • 7352 posts
  • Version:Unknown

Posted 02 October 2007 - 08:38 PM

The way I see it, a pixel is in the outline set if and only if it has at least one transparent neighbor.


Even though it's rare nowadays, you'd have to watch out for dithering in a case like that. If we're going for a single outline (i.e. not putting an outline on holes in the sprite), then a pixel should be considered an outline pixel if and only if there's a path from that pixel to the edge of the sprite such that that path only traverses transparent pixels. One way to find these is to flood fill from the outside inwards. Every "barrier" pixel that the flood fill hits is an outline pixel
  • 0

#21 EricDB

EricDB

    Eric Burgess

  • GMC Elder
  • 920 posts
  • Version:GM8

Posted 02 October 2007 - 09:12 PM

I implemented a simpler method...I don't have time to describe it right now, but here's the GMK. On my machine, it takes 78 miliseconds for a very convoluted 128x128 sprite, which isn't fast enough for use in a step event, but it's more than sufficient for pre-processing of images.

Edited by EricDB, 02 October 2007 - 10:14 PM.

  • 0

#22 cambesa

cambesa

    GMC Member

  • GMC Member
  • 868 posts
  • Version:Unknown

Posted 03 October 2007 - 03:06 PM

i want to save that outline in a list with x1,x2 y1 and y2.
from there on i can get the normal of the line of the colision, what is needed for the physics.
and when i dont use lines, the light will be very slow because the light makes a shadow based on the outline of an object and direction.

and yes, i just want to do it in creation event from an object.
after that when its in a list i can change the values used in my formulas using the midpoint, angle and length direction.
that is a looped script so one more reason for using lines instead of coordinates.
i use 2 things for my engine, box2d.
its a c++ scripted physics engine what uses lines too.
i want to change that c++ in gml and use its calculations to make my physics.
i also use this site for light: http://www.gamedev.n...s/2dsoftshadow/
thats c++ too and i want to change those calculations to gml too.
  • 0

Insanely large signature removed by a moderator.

(I've had that signature for decades but okay...)


#23 xot

xot

    GMC Dismember

  • GMC Elder
  • 4785 posts
  • Version:GM:Studio

Posted 04 October 2007 - 03:50 AM

That's pretty slick, EricDB.
  • 0
GMLscripts.com, rise from your grave!

If any of my posts contain broken images or links, I can probably supply them for you. PM with a link to the post.