Jump to content
  • Advertisement
Sign in to follow this  
ryoshirou

Polygon Selection

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

Hello,
 
I am making a 3D modeling application and I am currently stuck at polygon (face) selection. When I get the mouse coordinates, I project them into the scene and then with ray triangle intersection I find the right face. It works as expected, the only problem being performance. With high poly meshes, the application starts to slow down. Should I use a physics library for this? Is there an algorithm for selecting a polygon, regardless of the number of polygons?

Share this post


Link to post
Share on other sites
Advertisement
The trick is to use some kind of spatial partitioning, such as a BSP tree. The naive approach I assume you're using is iterating over all N polygons until you find a match, meaning that you have an O(N) algorithm.

Good spatial partitioning would turn this into an O(logN) algorithm. You might also find that you can rewrite your data structures and algorithm to make far better use of SIMD and better use of the CPU pipeline/cache. Note that SIMD would only give you a linear speed increase, but can often make the difference between a "fast O(N)" and a "slow O(logN)" for certain ranges of N.

You don't need a "physics" library per se, but a physics library would likely include a high quality spatial data structure.

Share this post


Link to post
Share on other sites

I'm not sure how it stacks up but you could also consider a render based solution. You render the whole model with an individual color/id per face to a texture and check the color/value of the area under where the mouse was. I don't know about the big O of that but it should be less than O(N). If you can use integer values then that gives you a lot of faces.

Share this post


Link to post
Share on other sites

You still do not need a BSP spatial atomizing, just examine what AABSs (axis aligned bound spheres) or AABBs ( axis aligned boundig boxes) are penetrating unlimtited ray, and do test those geometries in detail afterward.

If you can even pre examine by the depth/distance order of them, you are well saved of arbitrary scene complexity influencing a ray cast test :)

 

If your scene objects does not cary a trivial information of its AABS (4 numbers, 3d postion and radius) forget about BSP trees at that very point.

 

Share this post


Link to post
Share on other sites

I'm not sure how it stacks up but you could also consider a render based solution. You render the whole model with an individual color/id per face to a texture and check the color/value of the area under where the mouse was. I don't know about the big O of that but it should be less than O(N). If you can use integer values then that gives you a lot of faces.

 

I don't know if there are better more-modern ways, but this is the approach I'd go with.

 

Especially since in many situations, you're actually not wanting each triangle, but entire objects. i.e render an entire object as a solid color to an invisible offscreen buffer (even of half resolution), and if the mouse is over that invisible color, then the mouse is over that object. Or each face of a wall being a different color, for texturing a single face.

 

Further, you aren't constrained to triangles either. What if you want to select vertices? Just render the vertices as circles (or small triangles) with different colors in your offscreen buffer.

Share this post


Link to post
Share on other sites

I'm not sure how it stacks up but you could also consider a render based solution. You render the whole model with an individual color/id per face to a texture and check the color/value of the area under where the mouse was. I don't know about the big O of that but it should be less than O(N). If you can use integer values then that gives you a lot of faces.


Problem is, I also need to calculate the intersection point. I am using that information to position my 3D cursor. So color picking doesn't really apply here.
 

If your scene objects does not cary a trivial information of its AABS (4 numbers, 3d postion and radius) forget about BSP trees at that very point.


I'm not sure I understand what you mean.

How is object picking done in other software? Like Maya, Max, Zbrush?

Share this post


Link to post
Share on other sites

Problem is, I also need to calculate the intersection point. I am using that information to position my 3D cursor. So color picking doesn't really apply here.

 

You can still use rasterization to find the triangle at the specific point, then you can use math to find the exact intersection point between the selection ray and that specific triangle.

 

That said, I think it is more reasonable to make distinct separation between working with dense meshes (sculpting) and "regular" meshes modeled by hand. This will make it easier for you as a programmer, and users will not object to having two different workflows for both kinds of models, as that's generally the standard approach.

Share this post


Link to post
Share on other sites

You can still use rasterization to find the triangle at the specific point, then you can use math to find the exact intersection point between the selection ray and that specific triangle.
 
That said, I think it is more reasonable to make distinct separation between working with dense meshes (sculpting) and "regular" meshes modeled by hand. This will make it easier for you as a programmer, and users will not object to having two different workflows for both kinds of models, as that's generally the standard approach.


That could actually work. Thanks. In terms of programming, what kind of distinction are you talking about?

Share this post


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

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!