0

I need to determine if point lies inside shape. In case our shape is circle it's easy:

highp vec2 textureCoordinateToUse = vec2(textureCoordinate.x, (textureCoordinate.y * aspectRatio + 0.5 - 0.5 * aspectRatio));
highp float dist = distance(center, textureCoordinateToUse);
textureCoordinateToUse = textureCoordinate;
if (dist < radius) {
    ...
}

But what if my shape is star, hexagon, spirale or etc? Does somebody know any fast way to do it? May I use images with alpha channels as shapes? How to do it?

UPDATE: I have just understand that the best option now is to pass another texture to shader. How can I do it? Now shader has 2 properties: varying highp vec2 textureCoordinate; and uniform sampler2D inputImageTexture;. And I want to pass another texture to check alpha channel of it inside shader code.

UPDATE 2: I have tried to load shape to shader (I think so). I'm using GPUImage framework, so I have set sampler2D with my shape to uniform and tried to check alpha channel there. Is it okay? On my iPhone 5s it's looks very well, but what about performance?

Timur Bernikovich
  • 5,660
  • 4
  • 45
  • 58
  • Is this question about algorithms or existing libraries? – Eli Algranti Jul 21 '14 at 11:15
  • @EliAlgranti it's question about solution. I have no experience in OpenGL, but I can't find any tutorials about this. I think there is no existing libraries, but I hope there is way to convert .png with alpha channel to matrix for example and then check alpha of special pixel. – Timur Bernikovich Jul 21 '14 at 11:18
  • Just noticed the tags in your question so I can't give you a good answer. The problem you describe is known as the point in polygon (PIP) problem. You might try to look for solutions using this name. Wikipedia has more information and description of common algorithms to solve this problem (http://en.wikipedia.org/wiki/Point_in_polygon) – Eli Algranti Jul 21 '14 at 11:21

3 Answers3

1

If you can have an analytic shape representation such as circle all you need to find is an equation that describes that shape.

If you have a pre-drawn shape and you can pack it into a texture you can do that as well. All you need is to treat the object as a rectangle (a whole texture image) and do a rectangle check such as for the circle plus get the colour of that texture and do a colour check. What to check in colour really depends on you, it can be black-white, use the alpha channel.. anything really.

If you have a complex drawn object such as 3D model you need to get a model projection (silhouette) which can be drawn to a frame buffer object and again used as a texture or better yet try to draw it directly to the scene using some additional buffer such as stencil which you can then again use in fragment shader to check a specific value.

Matic Oblak
  • 16,318
  • 3
  • 24
  • 43
  • Adding some information to this reply, I can say the solution would go from : 1) find the equation which determines the shape you are dealing with (2D,3D) 2) one youve got the calculations done, know where your shape begins in the screen (given an X0 and Y0) 3) determine if the point is inside by using the equation because you know the area of the shape. Other way would be using a mask and invert the colors, but it´s not dynamic and it only serves for static images. – AlfuryDB Jul 21 '14 at 14:11
  • So, I have to pass shape texture to main() method of the shader and check alpha channel there? Will it be fast enough? My shapes can't be represented as equations. – Timur Bernikovich Jul 21 '14 at 14:13
  • If you want to have the same result as described in the question then the answer is yes. – Matic Oblak Jul 21 '14 at 14:14
1

For arbitrary polygonal shape: 1. Triangulate you shape (for example using Delaunay triangulation). 2. Check you point against every triangle. It is trivial. 3. Improve performance by using bounding shapes around original polygonal shapes and space partitioning for triangles.

game development germ
  • 1,324
  • 7
  • 21
  • My shapes can be not arbitrary polygonal. For example square with rounded corners. – Timur Bernikovich Jul 21 '14 at 17:56
  • 1
    And how do you render it? You must convert it in to point list which is exactly an arbitrary polygonal shape. Probably the question is that how many different shape types you want to support. If the number is a hundreds then you must use the most common method, in this case it is triangualtion. If you want to support squares and squares with rounded corners then use algebraic methods. – game development germ Jul 22 '14 at 08:07
  • I need to support even such shapes that have no name. :) How can I do it? I have *.psd with vector shape. – Timur Bernikovich Jul 22 '14 at 08:27
  • 1) Extract point list from PSD. If you have spline paths then you must resample splines in to line segments. 2) Feed the point list to appropriate triangulation algorithm. Considering that your shape may be concave hull with holes you may want to take a look at Clipper library (originally it is for polygonal clipping, but you can always preset a point as a degenerate polygon). – game development germ Jul 22 '14 at 08:57
1

A shader won't give you anything because the result of shader's routine is an image.

In image-based approach the problem need to be reformulated. Lets say you have a grayscale image with rendered shapes where white and gray pixels define shapes and black pixels define nothing. You must know the center of each shape and the bounding circle of each shape. Note that bounding circles of shapes must not intersect each other.

Then you can probe a point agains shapes first by bounding circles (this probe is necessary to distinguish shapes because by peeking a pixel from image you can only know if you point intersect some shape), and second by peeking a certain pixel. If both probes are positive then your point is inside of a shape.

game development germ
  • 1,324
  • 7
  • 21