Jump to content

  • Log In with Google      Sign In   
  • Create Account

Interested in a FREE copy of HTML5 game maker Construct 2?

We'll be giving away three Personal Edition licences in next Tuesday's GDNet Direct email newsletter!

Sign up from the right-hand sidebar on our homepage and read Tuesday's newsletter for details!


Picking objects


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
13 replies to this topic

#1 Yura   Members   -  Reputation: 263

Like
0Likes
Like

Posted 19 March 2013 - 05:26 AM

I know picking objects is well covered topic, nevertheless I have problems with it and asking you to help me.

So, my objective is to select (pick) some primitive on the screen, surround picked object with some border (for visibility) and return list of it's vertices.

 Code samples, which I found in internet are built about "primitive structures" - each primitive, like line, triangle, rectangle, etc. has it's  representation class with data of each primitive. In my program I use a little different approach: I have 1 global vertexBuffer and IndexBuffer. Those buffers contain locked data of whole figure, which can have very much different primitives. I need to pick some of those primitives. Is it possible with such project structure?

 



Sponsor:

#2 slicer4ever   Crossbones+   -  Reputation: 3943

Like
2Likes
Like

Posted 19 March 2013 - 05:50 AM

you could theoretically do ray->triangle test, iterate over all the triangles on your mesh and discover what polygon you are intersecting.  But that's horrible inefficient.  Do note that you could speed this up with quad trees, and such, but overall it's not an approach i'd use.

 

Unless this is an modeling software, then i'd likely store simpler objects to represent your object(or objects), and test against those, instead of the entire model.

 

Could you be a bit more descriptive on what your setup and goal is?


Check out https://www.facebook.com/LiquidGames for some great games made by me on the Playstation Mobile market.

#3 kauna   Crossbones+   -  Reputation: 2742

Like
2Likes
Like

Posted 19 March 2013 - 08:12 AM

Typically picking and "vertex / index buffers" don't fit in the same sentence. Reading data from vertex buffer isn't usually good idea. You should keep a separate copy of your vertex / primitive data and use it for picking.

 

The general work flow for picking goes something like:

 

- generate ray based on mouse position on screen and camera location

- for each object / entity / mesh calculate inverse world matrix to transform ray from the world space to the meshes local space

- test each surface/triangle with ray-triangle hit test. Choose the closest hit to the camera. 

 

Cheers!



#4 Yura   Members   -  Reputation: 263

Like
0Likes
Like

Posted 20 March 2013 - 02:20 AM

Reading data from vertex buffer isn't usually good idea.

VertexBuffer + IndexBuffer are very nice for my type of data settings. Comfortably to build and use.

In general, I have very massive models, more then 6 000 000 primitives, and VB + IB shows great efficient in working with such models. Can you say the same about separate copies of primitives? If yes, I'm ready to rebuild geometry for using this method.


 



#5 Yura   Members   -  Reputation: 263

Like
0Likes
Like

Posted 20 March 2013 - 03:08 AM

you could theoretically do ray->triangle test, iterate over all the triangles on your mesh and discover what polygon you are intersecting.  But that's horrible inefficient.  Do note that you could speed this up with quad trees, and such, but overall it's not an approach i'd use.

 

Unless this is an modeling software, then i'd likely store simpler objects to represent your object(or objects), and test against those, instead of the entire model.

 

Could you be a bit more descriptive on what your setup and goal is?

 

 

So, I have 2 collections: a collection of Elements, and a collection of Vertices. I take all vertices and add them to the vertex buffer.

Then I build IndexBuffer, using information from the collection of elements. Each element store information (ID) of vertices, which belongs to it. Several different elements can contain same vertex (or vertices).

 

By picking I want choose some element (primitive) on the screen and print information about it's vertices.



#6 Jason Z   Crossbones+   -  Reputation: 5147

Like
2Likes
Like

Posted 20 March 2013 - 04:55 AM

Since your scene content is not sorted in a data structure already, you will have a hard time to do any intelligent optimization of the ray picking.  Is it possible for you to use your vertex buffer as a data structure and store the vertex information related to its spatial location?  If so, you could then only do the ray intersection tests on a subset of the total primitives, which is what you are really after.

 

Other than that, you could try just clustering the vertex data near eachother, or perhaps even store separate buffers for different regions of your scene.



#7 slicer4ever   Crossbones+   -  Reputation: 3943

Like
1Likes
Like

Posted 20 March 2013 - 08:39 AM

you could theoretically do ray->triangle test, iterate over all the triangles on your mesh and discover what polygon you are intersecting.  But that's horrible inefficient.  Do note that you could speed this up with quad trees, and such, but overall it's not an approach i'd use.

 

Unless this is an modeling software, then i'd likely store simpler objects to represent your object(or objects), and test against those, instead of the entire model.

 

Could you be a bit more descriptive on what your setup and goal is?

 

 

So, I have 2 collections: a collection of Elements, and a collection of Vertices. I take all vertices and add them to the vertex buffer.

Then I build IndexBuffer, using information from the collection of elements. Each element store information (ID) of vertices, which belongs to it. Several different elements can contain same vertex (or vertices).

 

By picking I want choose some element (primitive) on the screen and print information about it's vertices.

 

So, from my understanding the easiest method right now(but also the slowest), is to iterate over each polyon, and do ray testing.

 

However, If i were doing this, and knew i needed to be able to pick certain vertices(or polygons).  I would probably try to create quad tree's for better optimizing what to select.

 

Remember that you don't have to use that vertex/index buffer for anything other than rendering.  It's common practice to use highly detailed models for actual rendering, and simple primitive's(aabb, obb, sphere's, etc) to represent the object in your game's logic.  I don't know what your full goal is(do you need to be able to pick a face, and modify that face, or...?)


Edited by slicer4ever, 21 March 2013 - 03:20 AM.

Check out https://www.facebook.com/LiquidGames for some great games made by me on the Playstation Mobile market.

#8 Yura   Members   -  Reputation: 263

Like
0Likes
Like

Posted 21 March 2013 - 02:14 AM

Remember that you don't have to use that vertex/index buffer for anything other than rendering.  It's common practice to use highly detailed models for actual rendering, and simple primitive's(aabb, obb, sphere's, etc) to represent the object in your game's logic.  I don't know what your full goal is(do you need to be able to pick a face, and modify that face, or...?)

 

 

Interesting.. And if I'll make those simple primitives classes, would it help? If I'll keep my buffers for rendering and create such classes for each element representation? How do I then connect those classes with image on the screen ?

I need fast method, I have prety much primitives and iteration over them all is not a good solution for me..

My full goal is to get information about picked element - it's type and vertices. No other manipulations are needed (at least yet smile.png )

 

Since your scene content is not sorted in a data structure already, you will have a hard time to do any intelligent optimization of the ray picking.  Is it possible for you to use your vertex buffer as a data structure and store the vertex information related to its spatial location?  If so, you could then only do the ray intersection tests on a subset of the total primitives, which is what you are really after.

 

Other than that, you could try just clustering the vertex data near eachother, or perhaps even store separate buffers for different regions of your scene.

 

It is sorted, but quite specifically.  I have Elements - generic collection, which contain data about each primitive (list of vertices, type, etc). I can't change it (it's a library), but I can try to use it in my purposes, to represent the object in logic, for example... I can use some technics or patterns to expand this collection with needed methods, like intersection. But I dont understand one thing - how do I connect those classes with image on the screen, image, taken from buffers ?


Edited by Yura, 21 March 2013 - 02:27 AM.


#9 user88   Members   -  Reputation: 268

Like
1Likes
Like

Posted 21 March 2013 - 03:44 AM

- how do I connect those classes with image on the screen, image, taken from buffers ?

 

Have already implemented the basic functionality of picking. I mean Pick ray calculation, from picked screen coordinates, etc?

 

In case you have a lot of 3D objects in scene you can make the map table of relationships between 3D object in scene and object in your application data model. You have to do it once per scene/level creation.



#10 Yura   Members   -  Reputation: 263

Like
0Likes
Like

Posted 21 March 2013 - 04:18 AM

- how do I connect those classes with image on the screen, image, taken from buffers ?

 

Have already implemented the basic functionality of picking. I mean Pick ray calculation, from picked screen coordinates, etc?

 

In case you have a lot of 3D objects in scene you can make the map table of relationships between 3D object in scene and object in your application data model. You have to do it once per scene/level creation.

 

I had found some methods to check picking, like this:

public static bool CheckPicking(Viewport viewport, BoundingBox bBox, Vector2 coord, Matrix mViewProj, out float distance)
        {
            Vector3 ZNearPlane = Vector3.Unproject(new Vector3(coord, 0), 0, 0, viewport.Width, viewport.Height, viewport.MinZ, viewport.MaxZ, mViewProj);
            Vector3 ZFarPlane = Vector3.Unproject(new Vector3(coord, 1), 0, 0, viewport.Width, viewport.Height, viewport.MinZ, viewport.MaxZ, mViewProj);

            Vector3 direction = ZFarPlane - ZNearPlane;
            direction.Normalize();

            Ray ray = new Ray(ZNearPlane, direction);

            if (ray.Intersects(ref bBox, out distance))
                return true;
            
            return false;
        }

 

This method checks intersection with some object (Bounding box, triangle, sphere or plane). It can be used to calculate intersection with concrette figure by iteration over all collection, but it is not the best desision. I'm looking for better solution...



#11 user88   Members   -  Reputation: 268

Like
1Likes
Like

Posted 21 March 2013 - 04:32 AM

I guess you use c#. Here is c# class representing triangle mesh. You can use picking functionality from this code:

/// <summary:
    /// 3D Geometry that consist from indices, vertices, normals, texture coordinates.
    /// </summary>
    public sealed class TriangleMesh
    {
        private static uint s_internalIdCounter;

	    private BoundingSphere m_boundingSphere;
	    private BoundingBox m_boundingBox;

        /// <summary>
        /// Gets an internal ID that value is unique for each instance.
        /// </summary>
        public uint InternalID { get; private set; }

	    /// <summary>
        /// Gets an array of the indices of the geometry.
        /// </summary>
        public ushort[] Indices { get; private set; }

	    /// <summary>
	    /// Gets an array of the vertices of the geometry.
	    /// </summary>
        public Float3[] Vertices { get; private set; }

	    /// <summary>
	    /// Gets an array of the normals of the geometry. Value can be <c>null</c>.
	    /// </summary>
        public Float3[] Normals { get; private set; }

	    /// <summary>
	    /// Gets an array of the normals of the geometry. Value can be <c>null</c>.
	    /// </summary>
        public Float2[] TexCoords { get; private set; }

	    public TriangleMesh(ushort[] indices, Float3[] vertices, Float3[] normals, Float2[] texCoords)
	    {
            if (indices.Length < 3)
                throw new ArgumentException("The length of the indices array shouldn't be less than 3 elements.", "indices");
            if (vertices.Length < 3)
                throw new ArgumentException("The length of the vertices array shouldn't be less than 3 elements.", "vertices");

	        Indices = indices;
	        Vertices = vertices;
	        Normals = normals;
	        TexCoords = texCoords;

	        unchecked
	        {
	            s_internalIdCounter++;
	        }
	        InternalID = s_internalIdCounter;

	        CalculateBounds();
	    }

        /// <summary>
        /// Calculates a bounding box and a bonding sphere of the geometry.
        /// </summary>
	    private void CalculateBounds()
	    {
	        m_boundingBox = BoundingBox.FromPoints(Vertices);
	        m_boundingSphere = BoundingSphere.FromBox(m_boundingBox);
	    }

        /// <summary>
        /// Gets transformed bounding sphere of the geometry.
        /// </summary>
        /// <param name="transform">Transformation matrix.</param>
        /// <returns>Transformed bounding sphere.</returns>
        public BoundingSphere CalculateBoundingSphere(Float4x4 transform)
        {
            Float3 center = Float3.TransformCoordinate(m_boundingSphere.Center, transform);
            return new BoundingSphere(center, m_boundingSphere.Radius);
        }

        /// <summary>
        /// Gets transformed bounding box of the geometry.
        /// </summary>
        /// <param name="transform">Transformation matrix.</param>
        /// <returns>Transformed bounding box.</returns>
        public BoundingBox CalculateBoundingBox(Float4x4 transform)
        {
            Float3 min = Float3.TransformCoordinate(m_boundingBox.Minimum, transform);
            Float3 max = Float3.TransformCoordinate(m_boundingBox.Maximum, transform);
            return new BoundingBox(min, max);
        }

        /// <summary>
        /// Determines whether a ray intersects the geometry.
        /// </summary>
        /// <param name="transform">Transformation matrix of the geometry</param>
        /// <param name="ray">The ray which will be tested for intersection.</param>
        /// <param name="distance">When the method completes, contains the distance at which the ray intersected the plane.</param>
        /// <param name="faceIndex">When the method completes, contains the index of face which the ray intersects.</param>
        /// <returns><c>true</c> if the ray intersects the plane; otherwise, <c>false</c>.</returns>
        public bool Intersects(Float4x4 transform, Ray ray, out float distance, out int faceIndex)
        {
            float u, v;
            return Intersects(transform , ray, out distance, out faceIndex, out u, out v);
        }

        /// <summary>
        /// Determines whether a ray intersects the geometry.
        /// </summary>
        /// <param name="transform">Transformation matrix of the geometry</param>
        /// <param name="ray">The ray which will be tested for intersection.</param>
        /// <param name="distance">When the method completes, contains the distance at which the ray intersected the plane.</param>
        /// <param name="faceIndex">When the method completes, contains the index of face which the ray intersects.</param>
        /// <param name="u">Barycentric U of face which the ray intersects.</param>
        /// <param name="v">Barycentric V of face which the ray intersects.</param>
        /// <returns><c>true</c> if the ray intersects the plane; otherwise, <c>false</c>.</returns>
        public bool Intersects(Float4x4 transform, Ray ray, out float distance, out int faceIndex, out float u, out float v)
        {
            // Convert ray to model space
            Float3 near = ray.Position;
            Float3 dir = ray.Direction;
            transform.Invert();
            Float3 tmp = near;
            Float3.TransformCoordinate(ref tmp, ref transform, out near);
            tmp = dir;
            Float3.TransformNormal(ref tmp, ref transform, out dir);
            Ray modelSpaceRay = new Ray(near, dir);

            // Test bounding sphere first
            BoundingSphere bs = CalculateBoundingSphere(transform);
            if (Ray.Intersects(ray, bs, out distance))
            {
                if (Indices != null && Indices.Length > 0)
                {
                    // Intersect indexed geometry
                    for (faceIndex = 0; faceIndex < Indices.Length; faceIndex += 3)
                    {
                        Float3 vertex1 = Vertices[Indices[faceIndex]];
                        Float3 vertex2 = Vertices[Indices[faceIndex + 1]];
                        Float3 vertex3 = Vertices[Indices[faceIndex + 2]];

                        if (Ray.Intersects(modelSpaceRay, vertex1, vertex2, vertex3, out distance, out u, out v))
                        {
                            return true;
                        }
                    }
                }
                else
                {
                    // Intersect non-indexed geometry
                    for (faceIndex = 0; faceIndex < Vertices.Length; faceIndex += 3)
                    {
                        Float3 vertex1 = Vertices[faceIndex];
                        Float3 vertex2 = Vertices[faceIndex + 1];
                        Float3 vertex3 = Vertices[faceIndex + 2];

                        if (Ray.Intersects(modelSpaceRay, vertex1, vertex2, vertex3, out distance, out u, out v))
                        {
                            return true;
                        }
                    }
                }
            }

            faceIndex = -1;
            distance = u = v = -1f;
            return false;
        }

        /// <summary>
        /// Determines whether a ray intersects the geometry.
        /// </summary>
        /// <param name="transform">Transformation matrix of the geometry</param>
        /// <param name="ray">The ray which will be tested for intersection.</param>
        /// <param name="distance">When the method completes, contains the distance at which the ray intersected the plane.</param>
        /// <param name="faceIndex">When the method completes, contains the index of face which the ray intersects.</param>
        /// <param name="hits">All intersection hits.</param>
        /// <returns><c>true</c> if the ray intersects the plane; otherwise, <c>false</c>.</returns>
        public bool Intersects(Float4x4 transform, Ray ray, out float distance, out int faceIndex, out IntersectInformation[] hits)
        {
            var hitsList = new List<IntersectInformation>();
            
            float curDistance;
            int curIndex;
            
            distance = float.MaxValue;
            faceIndex = -1;

            // Create bounding sphere before inverting transform matrix
            BoundingSphere bs = CalculateBoundingSphere(transform);
            
            // Convert ray to model space
            Float3 near = ray.Position;
            Float3 dir = ray.Direction;
            transform.Invert();
            Float3 tmp = near;
            Float3.TransformCoordinate(ref tmp, ref transform, out near);
            tmp = dir;
            Float3.TransformNormal(ref tmp, ref transform, out dir);
            Ray modelSpaceRay = new Ray(near, dir);

            // Test bounding sphere first
            if (Ray.Intersects(ray, bs, out curDistance))
            {
                if (Indices != null && Indices.Length > 0)
                {
                    // Intersect indexed geometry
                    for (curIndex = 0; curIndex < Indices.Length; curIndex += 3)
                    {
                        Float3 vertex1 = Vertices[Indices[curIndex]];
                        Float3 vertex2 = Vertices[Indices[curIndex + 1]];
                        Float3 vertex3 = Vertices[Indices[curIndex + 2]];

                        float u, v;
                        if (Ray.Intersects(modelSpaceRay, vertex1, vertex2, vertex3, out curDistance, out u, out v))
                        {
                            if (curDistance < distance)
                            {
                                distance = curDistance;
                                faceIndex = curIndex / 3;
                            }

                            var hit = new IntersectInformation
                                          {
                                              Distance = curDistance,
                                              FaceIndex = faceIndex,
                                              U = u,
                                              V = v
                                          };
                            hitsList.Add(hit);
                        }
                    }
                }
                else
                {
                    // Intersect non-indexed geometry
                    for (curIndex = 0; curIndex < Vertices.Length; curIndex += 3)
                    {
                        Float3 vertex1 = Vertices[curIndex];
                        Float3 vertex2 = Vertices[curIndex + 1];
                        Float3 vertex3 = Vertices[curIndex + 2];

                        float u, v; 
                        if (Ray.Intersects(modelSpaceRay, vertex1, vertex2, vertex3, out curDistance, out u, out v))
                        {
                            if (curDistance < distance)
                            {
                                distance = curDistance;
                                faceIndex = curIndex / 3;
                            }

                            var hit = new IntersectInformation
                            {
                                Distance = curDistance,
                                FaceIndex = faceIndex,
                                U = u,
                                V = v
                            };
                            hitsList.Add(hit);
                        }
                    }
                }
            }

            hits = hitsList.ToArray();
            return hits.Length > 0;
        }
    }

 

Also ray you have to get from picked pixel on screen rather than from near/far. Have a look to this code:

 

void CalculatePickRay(int x, int y, int width, int height, float near, Float4x4 view, Float4x4 projection, out Float3 pickRayDir, out Float3 pickRayOrig)
        {
            pickRayDir.X = (((2.0f * x) / width) - 1);
            pickRayDir.Y = -(((2.0f * y) / height) - 1);
            pickRayDir.Z = 1.0f;

            projection.M41 = 0;
            projection.M42 = 0;
            projection.M43 = 0;
            projection.M44 = 1;
            projection.Invert();
            Float3 tmp = pickRayDir;
            Float3.TransformNormal(ref tmp, ref projection, out pickRayDir);

            // Get the inverse view matrix
            view.Invert();
            tmp = pickRayDir;
            Float3.TransformNormal(ref tmp, ref view, out pickRayDir);
            pickRayDir.Normalize();

            pickRayOrig.X = view.M41;
            pickRayOrig.Y = view.M42;
            pickRayOrig.Z = view.M43;

            // calc origin as intersection with near frustum
            pickRayOrig += pickRayDir * near;
        }


#12 Jason Z   Crossbones+   -  Reputation: 5147

Like
3Likes
Like

Posted 21 March 2013 - 05:03 AM

Interesting.. And if I'll make those simple primitives classes, would it help? If I'll keep my buffers for rendering and create such classes for each element representation? How do I then connect those classes with image on the screen ?

I need fast method, I have prety much primitives and iteration over them all is not a good solution for me..

My full goal is to get information about picked element - it's type and vertices. No other manipulations are needed (at least yet )

After reading this, I think you might be better off with a false color picking operation.  Instead of trying to do this geometrically, you should instead render your elements with a special shader that produces an 'ID' color for its geometry.  Then when you want to do picking, you simply read the render target contents back to system memory and look up which 'ID' your cursor was over.

 

This flattens your problem - instead of iterating over N objects on the CPU (which has maximum up to 8 cores), you are rasterizing the scene with your GPU (which uses hundreds or thousands of cores) and then just retrieving the results.  I think in your situation, this would be a good solution.



#13 Yura   Members   -  Reputation: 263

Like
0Likes
Like

Posted 22 March 2013 - 03:22 AM

void CalculatePickRay(int x, int y, int width, int height, float near, Float4x4 view, Float4x4 projection, out Float3 pickRayDir, out Float3 pickRayOrig)
{
pickRayDir.X = (((2.0f * x) / width) - 1);
pickRayDir.Y = -(((2.0f * y) / height) - 1);
pickRayDir.Z = 1.0f;

 

On Picking Ray construction, what does input params mean?
x and y - mouse position, as far as I understand
width and height - Viewport width and height
float near - ????

 

And at public bool Intersects(Float4x4 transform...

transform - it's  a world matrix?



#14 Jason Z   Crossbones+   -  Reputation: 5147

Like
1Likes
Like

Posted 22 March 2013 - 05:13 AM

I'm not sure where you got these methods from, so I can't say definitively, but the typical inputs are as you described them.  You need the x,y mouse coordinates, the size of the onscreen area that the view and perspective matrices are being applied to (i.e. the current viewport), then the view and perspective matrices.  Basically you just need to construct a ray from the camera location (which is [0,0,0] in view space) to the point on the near clipping plane where the mouse cursor is.

 

The near clipping plane is probably what they are referring to with near.  About the intersects method, I'm not really sure.  The ray that you construct is typically supposed to be in world space, but it all depends on how you want to do the tests.






Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS