   determine vertex in an area determined
  Hi,I have 3D objects (sometimes 360° objects) in .obj format (so there is no real order in the points and triangles to facilitate calculations) and an object can have more than 500 000 points and so 1000 000 of triangles.Now i would like to be able to delimitate a region on the surface of the 3D object. To do this i have choosen to select points on the surface and then i link the first choosen point with the second and the second with the third.... and the last with the first. So i have a delimited surface on my 3D object.Ex : five points which delimitate an area : (don't know how to include image directly in the message) http://photobucket.com/albums/y36/ioda100/?action=view&current=area_5pts.jpgThe points are connected 2 by 2 by a line on the surface found by cutting the 3D object by plans pasing by these 2 points and we choose the plan which gives the shortest line (so we know the equation of the plan for each line).The problem is now that i have delimited an area to determine all the points inside this area to for example apply a filter only on these points of the surface...To solve this for the moment, i use the equations of the plans and for each point of the 3D object i make an inequation Ax + By + Cz + D < 0 or > 0 and if the point satisfy the good inequation for all the plans, it is inside the area.This method is ok if the surace delimited is convex but sometimes there is a second region delimited is we work with real 3D 360° object.And sometimes with patologic object that fails.ex :worked fine : http://photobucket.com/albums/y36/ioda100/?action=view&current=sphere_ok.jpgfailed 2 regions : http://photobucket.com/albums/y36/ioda100/?action=view&current=dino_2_zones.jpgfailed patologic : http://photobucket.com/albums/y36/ioda100/?action=view&current=prob_bosse.jpgSo i am searching for a method to remove the second region found when there is one and to deal with patologic case automatically.But a lot of software allow to select points in a surface like this so there is probably a better method to do this.But as said previously there is no real structure on the order of points and triangles. And object can have more than 500 000 pts and so 1000 000 triangles. So some method could be very slow.Now i have just a method to find second triangle which share an edge of a triangle.Thanks in advance for your help if you have ideas   
  Hi,I really don't know if what i'll say is good or not, but it might give you some ideas :First : you'll need to build connectivity informations : for each vertex, store pointers to vertices which are linked to it by a segment.Second : when you define an area, you create points on the surface. Let's say the first point is called A. Get the closest vertex to A such that it's inside the area (simply loop through the vertices, get the 10 closest vertices to A, and then test them to know if they are inside the area or not)Third : Add this vertex to an empty list. Now, loop through all the vertices which are connected to this one, and add them if they are inside the area (it's recursive, but pretty fast since you have to check directly connected vertices)And that's it, you have your area. The idea is to get a vertex which is inside the area, and then expand from it until all the vertices inside the area are selected.;  tout d'abord merci pour ta reponse puisque je suppose que tu parles francais  ;)Yes we advice me to go to a method which expand the area for this kind of problem.And i suppose i will be obliged to build a connectivity "graph" since i have no other way to directly know which point is the neighbor of a particular point. - the first problem is that to link 2 pts i use a "connectivity graph" for edge and it takes time to be build (2-3 sec) and for connectivity points it will be surely (5-6 sec) and it can be big structures with 500 000 pts. But i suppose it's necessary and later i can compute this with a second thread when all is idle.- for the second point, when you say find the closest points to A and test them. To test i suppose you mean with the equation of plans and make inequation? (i still will have problems with non-convex area). The same for testing all the points in fact.But i think it would be very harder to deal with non-convex area so i think i will have to modify non-convex area on a convex area.The problem will be to detect if the area is non-convex and to modify the area to make it convex.I think your idea is certainly very near the solution to have something not too slow. Mine was faster (no need to build connectivity graph of vertex) but difficult to remove the second unexpected region when there is one and difficult to deal with  pathologic cases.So the remaining problems would be : detect if region convex and if no, to make it convex.As i know equations of the plans, we can compute angles between consecutive plans. if A B C D are the coefficients of one plane so we have (A B C) for the normal to this plan (or -A -B -C have to test with a point we know inside but to know if a point is inside we need to make inequations and then to be sure if we use A B C D or -A -B -C -D... so something to solve there)Then we can compute angles between normals of consecutive plans with cross product and arcsin and if the angle is positive, to move the vertex and test in angle if negative...Or i can simply say : use convex area or if not, display a msg to say that all the pts won't be found.   ;  Ioda : check your private messages, I sent you one.(sorry for bumping this thread just to say that ^^'')   ;Quote:Original post by paicIoda : check your private messages, I sent you one.(sorry for bumping this thread just to say that ^^'')thx i've replied by this way too.easier in french  ;)   ;  Just in case (because when Mesh are made of +/- 1 000 000 pts and so 2 000 000 it's pretty slow and connectivity graph is big in memory +/- 200MB), is it possible tu use opengl feature to select a region? I've seen softwares (like rapidform i think) that select a region by only surround a region with the mouse and the region is selected very fast even with big objects. I don't know how they do but it seem very good.They load obj files too and i don't think they use a connectivity graph or something like this because it's pretty fast.If you have ideas of how they could do this..If no, i will continue on this. But the more i advance the more i realize it's an heavy and slow method to select an area on my triangle mesh.Thx   