Hey guys!!!
I have a question again:
Do somebody of you know a fast way to find the closest vertex to the the eye camera?
The first idea, which popped into my mind was to read back the depth buffer and find the minimum depth value.
But this is a rather dirty solution. Are there better ones?
Thanks a lot!!!
remark: I meant CLOSEST vertex to camera, not closet 
[This message has been edited by A027298 (edited 01-16-2003).]
Pythogora’s Theorem?
Or am I missing something?
An if I have 100000 vertices. The whole thing should be in realtime.
BTW what exactly do you mean here with Pythagoras theorem?
[This message has been edited by A027298 (edited 01-16-2003).]
Hmmm…or is it possible to use maybe a vertex program to use the distance from the last processed vertex for the current processed vertex?
Originally posted by A027298:
An if I have 100000 vertices. The whole thing should be in realtime.
Build a hierarchical representation of your scene, e.g. an octree. That’ll help speed things up.
– Tom
BTW what exactly do you mean here with Pythagoras theorem?
A^2 + B^2 = C^2
I’m suprised you didn’t know this. This is stuff taught back in middle school, like 6th grade. One of the things taught when people first start to learn algebra as kids.
-SirKnight
Hey SirKnight, add disclaimer: some of us didn’t pay attention in school!
Originally posted by A027298:
An if I have 100000 vertices. The whole thing should be in realtime.
Shouldn’t be a problem. I just did a quick test on a machine with a modest modern processor, and 100000 vertices take about 2 milliseconds.
As mentioned above, there are other techniques which might be quicker depending on your problem (eg. is your geometry static, etc.).
Originally posted by Robbo:
Hey SirKnight, add disclaimer: some of us didn’t pay attention in school!
Maybe, but my god, this thing is taught/used in almost every math class after algebra is first taught to students. I’ve had to use it so much in the past ungodly amount of years in school that I probably know it better than my own name. But paying attention or not, one needs to know math before diving into a subject as math intensive as 3d graphics. 
-SirKnight
Use your scene graph. Assuming you have bounding volumes for each object, start like this:
cur_min = +Inf;
foreach obj in scene.objects
if distance( obj.center, camera ) - obj.radius < cur_min then
foreach vert in obj
if( distance( vert, camera ) < cur_min ) then
cur_min = distance( vert, camera )
endif
endfor
endif
endfor
This will only visit, on average, perhaps sqrt(N) vertices out of the scene. You can make it better with better bounding/dividing volumes in your scene graph.Originally posted by SirKnight:
[b] A^2 + B^2 = C^2
I’m suprised you didn’t know this. This is stuff taught back in middle school, like 6th grade. One of the things taught when people first start to learn algebra as kids.
-SirKnight[/b]
Oh sure I know this theorem. I learned this in the first years of school, like almost every kid around the world learning it. I just didn’t understand what nutball meant using this theorem in this context. To get the distance between the camera and a vertex I just would calc the vertex between the camera and this vert and normalize it.
@nutball
wow, thats fast. My scene is not too big but I cannot restrict it to be static. Maybe it’s faster than reading back the z-buffer.
Another thing what I thought about but maybe doesn’t work is to render it into a texture and find its min with a pixel shader or a texture shader. Could this work?
Pythagoras rulez! :-)))
[This message has been edited by A027298 (edited 01-16-2003).]
nutball,
I don’t understand why you mention Pythagora’s theorem here. Could you explain further?
For me, it has nothing to do with this theorem: it’s just an application of “calculating distance between two points” which is more using the euclidian norm:
V(x,y,z): vector
sqr(N(V))=xx+yy+z*z
Here, knowing where the viewer is (x0,y0,z0) and where each vertex is (xn,yn,zn) you’d get:
sqr(Nn)=sqr(xn-x0)+sqr(yn-y0)+sqr(zn-z0)
And you’d find your vertex by finding for which n you get the minimum…
I guess that depends on what you mean by “closest”. Is it closest to the camera location or closest to the “camera viewing plane” (in which case you’re looking for vertex to plane distance where Pythagora’s theorem can be used…)???
Regards,
Eric
Eric,
you’re talking of the same thing, but with a more contemporary formalism. The fact that one can define the vector norm as you’ve done is equivalent to pythagoreas’s theorem.
who was first? euclid or phytagoras? think, dudes 
btw, you don’t need the square root to sort…
and yes you should have at least some small tree structure… at least find closest mesh and then find closest point in the closest mesh… surely not find closest point of all possible points everywhere in the world…
Do you need the closest vertex in your scene, or the closest one that is actually drawn to the screen? Because all the methods you propose give the latter, and in that case there’s a little more to it than pythagoras.
-Ilkka
Originally posted by A027298:
I just didn’t understand what nutball meant using this theorem in this context. To get the distance between the camera and a vertex I just would calc the vertex between the camera and this vert and normalize it.
To normalise a vector you have to find its length. If you look at the expression which gives you this length, and compare it to Pythagoras Theorem, they’re remarkably similar.
[b]
@nutball
wow, thats fast. My scene is not too big but I cannot restrict it to be static. Maybe it’s faster than reading back the z-buffer.
Another thing what I thought about but maybe doesn’t work is to render it into a texture and find its min with a pixel shader or a texture shader. Could this work?
[/b]
It could, but it will quite likely be slower! Note that my tests were simply a few lines of plain C, I wasn’t using SIMD instructions.
The method I’m suggesting is very simple, and brute force. You’re basically testing every vertex.
If you have a tree (scene graph) then you should use it. If not, it’s not clear to me that building one just to do this test will be quicker than the brute force approach. Especially if you have to build it every frame. Though if you can do it one and re-use it, it may be quicker. Hence my comment about static geometry.
As has been pointed out, if what you want to do is find the closest vertex which is actually on the screen, then you have more work to do.
The best solution depends on your problem, and you haven’t given enough information about it for the rest of us to give you a definitive answer what the best approach is!
Finally there’s no substitute for trying different techniques for yourself to see which is faster. You want to know if rendering is faster than what I’ve suggest? Code it up and find out!
Originally posted by nutball:
The best solution depends on your problem, and you haven’t given enough information about it for the rest of us to give you a definitive answer what the best approach is!
Ok I try to give you more information:
I don’t use a tree structure and I think that it doesn’t make sense to build a tree to do this thing. But ok, what I actually wanna have before rendering the scene is to know the distance of the vertex closest to the camera position. Something like the following…
float func(vertex campos, vertices* verts, size) {
float fRet = FLT_MAX;
for(i = 0; i < size; i++) {
f = dist(campos, vertes[i]);
if(f < fRet)
fRet = f;
}
return fRet;
}
…I hope now everybody got me.
Originally posted by nutball:
Finally there’s no substitute for trying different techniques for yourself to see which is faster. You want to know if rendering is faster than what I’ve suggest? Code it up and find out!
I think I go for yours:
Here’s just a thought - if you were prepared to use the Z buffer, then maybe you don’t need to know the true euclidean distance, but only which vertex is closest to the near clipping plane? If so, you could just Z-sort your vertex buffer and grab the one with the smallest Z?
Originally posted by A027298:
[b]I think I go for yours:
- doing brute force
- using SIMD instructions
- no sqrts
As long I have only a vertexcount between 20k and 100k it should be ok. You needed only 2ms for 100000. What CPU did you use?
[/b]
That was on an Athlon MP 1600+.
Originally posted by NordFenris:
Here’s just a thought - if you were prepared to use the Z buffer, then maybe you don’t need to know the true euclidean distance, but only which vertex is closest to the near clipping plane? If so, you could just Z-sort your vertex buffer and grab the one with the smallest Z?
Would a sort be quicker? Don’t know. Maybe.
Sort? That doesn’t work unless you transform the vertices to eye space on the CPU!