I have an interesting task (#obscureProblem) that I thought some of you might be able to give some thoughts on..
The starting object is a surface mesh, this can be from any parametric model (a simple closed volume to start with, for example a cylinder, cuboid or sphere).There might potentially be an infinite number of unique meshes. For instance, using a z-map model of London and isolating each building and converting each to a surface mesh gives several thousand. And then extracting the vertices from those meshes gives a set of point clouds.
The problem is, every vertex needs to be uniquely identifiable. So with the typical vertex properties (X, Y, Z location on that building) some of the vertices will have the same identity. Bringing in more properties, like Normal X, Y, Z components, means there is more differentiation and less non-unique vertices.
The question is really, if you were to 'describe' a point on a object (a building) by some set of characteristics, so it is identifiable from all others everywhere else (unless in the very small set of cases where they are genuinely identical), what characteristics would you use? In fact, to start with, the X, Y and Z location of that point aren't very useful at all unless they are normalised, so the UVW properties have to be used.
sam
i may be not understanding fully but each mesh itself be the unique identifier. if you have a few thousand buildings that are represented by meshes then mesh[125]. vertices[0] be the first vert on building 125?
the other way to go is to be able to add a notation property to the feature that will let you tag each mesh with an identifier.
you're right that the most efficient way to identify them is by indexing like that, but i want to use intrinsic vertex properties instead. it's like if you were asked to re-invent postal addresses but without street names and numbers, using only building characteristics like 'height, brick, victorian, etc'. what is the minimum number of features needed to make each one unique.. so they can't be an index number or a reference tag.
You can be almost sure that the x,y,z tupple is unique, but that's not very interesting. What'd be more interesting would be classes of vertex. Yu could have all kinds of data structure fun with it. E.g. A tree structure where the first split was on number of faces that meet on that vert, then the angles that they make.
Th bigger question is "why?" to what end are you thinking about this?
The XYZ positions are unique when you have all the meshes in one model (city style), but when you separate them all out individually there are some similar ones. Actually I am using a decision tree so it's structured that way already, deciding on what decisions to make though is the problem.
The context is.. there is a machine learning algorithm (a random forest tree bagger in Matlab) that uses vertex properties to predict the 'behaviour' at that vertex. For instance, a point in a model might have a certain % of day light on it (this is the learning response output) which is a function of the properties at that point (vertex characteristics). On a sphere, you could say that DL%(VertexNormal) which is the simplest case, i think the normal direction is the only factor governing the day light % on a sphere. But what about on a more complex shape...
i think i tried to tackle a similar problem. I wanted to find a very efficient way to find duplicate points so i had to come up with a way to identify each point (give it an address). the brut forc way is to loop over the set twice checking if the x y and z were equal, if they were then its a dup point. but this is very slow for large amounts of points.
so i was wondering how do i identify a point with a unique address to check if another item lived there. my answer was to use a key value pair, in c# its call a dictionary. its similar to a generic list but it lets you add an address (key) to each member. so i used a string as the key and the value was a point. the nice thing about a dictionary is that keys must be unique so if a point had the same address (key) it would not be added to the list if the address was already in the list. the address i used was
x-y-z as a string so it would be something like "52.3235-89.2458-47.2548" . i used a string as the key because using the x y and z any other way could result in non unique address. the other great thing about this is a dictionary class is setup to be search by address(key) . so you can look up a point by its full address x-y-z or even better just look for a partial key, so look for a partial key "x-y" and it would return all points with that x any regardless of z .
perhaps this may help a little with your problem.
for what i was doing this ended up be a very fast way to search for duplicates. the only flaw i had was that because of double precision the last digit may be different causing the key to be unique. so i had to find a way to implement a 'fuzy address' that would allow me to enter a tolerance for what was considered a duplicate. in the end i settled on just rounding (you can also truncate the number) the x y z to a tolerance value to generate the key so i was able to adjust the precision that way.
Yea that's nearly there, but the problem is more what the descriptor should be. In your case you're using X, Y and Z, but there could be another 'coordinate system', with however many axes, that can describe a point. At the moment, by coordinate system is:
(Zposition relative to total height, Vertex Normal, Horizontal position relative to edge)
For an nD set converted to String, you can also use with a Hashset for removing duplicates. You can use to check for 'unique-ness' in a set, i.e. get the array size before and after passing through the hashset, gives a number of duplicates.
Came across this Siggraph presentation recently...
I wonder if looking at something like storing the irradiance values would be helpful. The specular calculation stuff also reminds me of another Siggraph paper by Pixar, that stores all kinds of lighting info as point clouds....
point clouds... vertices...mesh vertices...?
The specular calc is also interesting as there are GPU assisted ways to calculate between the camera view vector and the 'primary' light i.e. sun? Between these two angles and spatial locations, it should be possible to 'index' a scene in a data structure that is aligned to the 'amount of daylighting' mentioned. The irradiance stuff even has 'roughness' as an argument, which should be able to harness photographic survey info to distinguish glazed or reflective surfaces.
The Luxo render engine also makes use of an irradiance cache... A city mesh model that is texture mapped could be processed and a point cloud data structure used to store the irradiance info in addition to the 3d location info already stored in the mesh. Since daylighting is 'material' to whatever you are trying to do, it should make sense to incorporate the sun's position as a 'key' value. I guess, the other end of the specular calculation would be the point of view location...?