# closet vertex to camera.

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 &lt; cur_min then
foreach vert in obj
if( distance( vert, camera ) &lt; 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:

• 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?

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!