PDA

View Full Version : closet vertex to camera.



A027298
01-16-2003, 05:35 AM
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).]

nutball
01-16-2003, 05:39 AM
Pythogora's Theorem?

Or am I missing something?

A027298
01-16-2003, 05:47 AM
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).]

A027298
01-16-2003, 05:55 AM
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?

Tom Nuydens
01-16-2003, 06:13 AM
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

SirKnight
01-16-2003, 06:31 AM
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

Robbo
01-16-2003, 06:34 AM
Hey SirKnight, add disclaimer: some of us didn't pay attention in school!

nutball
01-16-2003, 07:22 AM
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.).

SirKnight
01-16-2003, 08:26 AM
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. http://www.opengl.org/discussion_boards/ubb/wink.gif But paying attention or not, one needs to know math before diving into a subject as math intensive as 3d graphics. http://www.opengl.org/discussion_boards/ubb/smile.gif

-SirKnight

jwatte
01-16-2003, 06:34 PM
Use your scene graph. Assuming you have bounding volumes for each object, start like this:

[CODE]
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.

A027298
01-16-2003, 06:53 PM
Originally posted by SirKnight:
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
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).]

Eric
01-17-2003, 12:36 AM
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))=x*x+y*y+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

Morglum
01-17-2003, 12:41 AM
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.

davepermen
01-17-2003, 12:47 AM
who was first? euclid or phytagoras? think, dudes http://www.opengl.org/discussion_boards/ubb/biggrin.gif

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..

JustHanging
01-17-2003, 02:16 AM
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

nutball
01-17-2003, 02:31 AM
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. http://www.opengl.org/discussion_boards/ubb/smile.gif



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


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!

A027298
01-17-2003, 03:44 AM
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?

NordFenris
01-17-2003, 04:01 AM
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?

nutball
01-17-2003, 04:48 AM
Originally posted by A027298:
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?


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.

Tom Nuydens
01-17-2003, 05:19 AM
Sort? That doesn't work unless you transform the vertices to eye space on the CPU!

A027298
01-17-2003, 05:57 AM
Originally posted by Tom Nuydens:
Sort? That doesn't work unless you transform the vertices to eye space on the CPU!
Yes, sorting would be ok but this transformation on the CPU is very expensive.

...could I use a vertex program like using the distance of the last vector and compare it with the current?

This would need something like a static variable/register and pass it back then to the application...?

[This message has been edited by A027298 (edited 01-17-2003).]

nutball
01-17-2003, 06:16 AM
Originally posted by A027298:

Yes, sorting would be ok but this transformation on the CPU is very expensive.


I think that was Toms point!



...could I use a vertex program like using the distance of the last vector and compare it with the current?

This would need something like a static variable/register and pass it back then to the application...?


You can't use a vertex program for precisely that reason. "Static" registers don't exist, and aren't likely to, as they cause all sorts of nasty race-conditions in the pipeline.

You seem rather afraid to do things on the CPU, and prefer to do them on the GPU, regardless of how complex that makes the operation. Is there a reason for this?

ScottManDeath
01-17-2003, 07:20 AM
Hi

Perhaps you can calculate the distance to the eye plane by doing the opengl projectio just for the z coordinates. After that the z position is divided by the w component. Finally the distances get sorted.




mvp2...row 2 of modelviewprojection matrix
mvp3...row 3 of modelviewprojection matrix
vertex... vertex in object space with 4 components

for all vertices do
dist= dot4(mvp2,vertex) / dot4(mvp3,vertex)
store distance and vertex index

sort(distances)



For storing I would us a STL map<float,int> because its automaticly sorted.

Perhaps this is not what you want, but its a possible way

Bye
ScottManDeath

A027298
01-17-2003, 05:43 PM
Originally posted by nutball:
You can't use a vertex program for precisely that reason. "Static" registers don't exist, and aren't likely to, as they cause all sorts of nasty race-conditions in the pipeline.

Ok I see...


Originally posted by nutball:

I think that was Toms point!

indeed... :-)


Originally posted by nutball:
You seem rather afraid to do things on the CPU, and prefer to do them on the GPU, regardless of how complex that makes the operation. Is there a reason for this?
No I am not afraid doing things on the CPU, but you know all vertices go to the GPU anyhow and why not perform then some stuff there?! ...instead going through all vertices twice on CPU and GPU. But as you already said, it doesn't work in the GPU.

@ScottManDeath
Thanks interesting idea, but maybe it's too much what I want. I only wanna know the distance to the closest vertex to the camera position.

Thanks guys!!!


[This message has been edited by A027298 (edited 01-17-2003).]

[This message has been edited by A027298 (edited 01-17-2003).]

WhatEver
01-17-2003, 07:39 PM
If you could tell us what effect you're trying to produce realtime, maybe we could tell you if it's possible to do it at acceptable speeds. From the little bit of info that you've shared with us I'd say that daves suggestion along with the Pythogora's Theorem without the sqrt would pretty much do what you want.

A027298
01-17-2003, 10:02 PM
Originally posted by WhatEver:
If you could tell us what effect you're trying to produce realtime, maybe we could tell you if it's possible to do it at acceptable speeds.
I would like to move the near plane as far as possible to the rendered scene. So I need to calculate the disctance to the vertex, which lies closest to the camera position.

Currently I am reading back the Z-Buffer. I render my scene only with a viewport like (0, 0, 128, 128) but I need then about 32 ms (gf4, P4). Thats slow. Nutball's idea is much much faster, but it makes only sense for static geometry. My scene is small I have no tree structure, about 20k-100k verts and I cannot be restricted to be static. So,...it's not more to say what I wanna do. Maybe there is an other clever idea, otherwise I have to go for the read back.

Thanks.

ScottManDeath
01-18-2003, 02:31 AM
Hi

when you just want to place the near clipping plane as deep as possible, I would think about my suggestions because they will give you the vertices distance to then near plane.
If you use the euclidian distance from vertex to your camera, you'll get different distances if your vertex is in center or on the border of your screen.

Another option would be to use the feedbackbuffer. IIRC it gives you the vertex window z depth. Then you just sort after it. The drawback is that you have to render your scene twice.

Bye
ScottManDeath

WhatEver
01-18-2003, 04:24 AM
Why do you need to know which vertex is closest? Are you trying to select vertices that are closest to the near plane?

A027298
01-18-2003, 06:32 AM
Originally posted by ScottManDeath:
when you just want to place the near clipping plane as deep as possible, I would think about my suggestions because they will give you the vertices distance to then near plane.

Hmmm...yes I should examine your suggestion. But why to store the vertices in a map? If the camera moves, all the vertices in the scene get a different transformation. So, why to use the old ones? But to that point you maybe didn't know what I exactly wanted.

I mentioned that I am currently reading back the depth buffer. Actually the major penalty is the rendering of the scene, not the read back of the depth buffer (!). The read back plus finding the smallest value costs me 0ms with GetTickCount(). To render the scene costs me 32 ms (of course, everything is disabled, except the depth buffer).


Originally posted by ScottManDeath:

Why do you need to know which vertex is closest? Are you trying to select vertices that are closest to the near plane?

I need it only to adjust the near plane. So I am not trying to select vertices closest to the near plane or something like that.


[This message has been edited by A027298 (edited 01-18-2003).]

WhatEver
01-18-2003, 08:59 AM
Why not just leave the near plane set to 1.0 or whatever your preference?

I appologize if I'm totally misunderstanding your intent, but from what I gather now, you want to adjust the near plane according to the closest vertex every frame for some reason. You don't need to do that. When you set the near clipping plane with glFrustum or glOrtho, it's always relative to the camera position.

Let me know if I'm on the right track.

A027298
01-18-2003, 09:50 PM
Originally posted by WhatEver:
I appologize if I'm totally misunderstanding your intent, but from what I gather now, you want to adjust the near plane according to the closest vertex every frame for some reason.
Exactly, I wanna do that every frame in a if possible very fast way.



Originally posted by WhatEver:
When you set the near clipping plane with glFrustum or glOrtho, it's always relative to the camera position.

Yes thats right, but you get different 'images' when moving the near plane. And for my thing I need it as close as possible to my scene.


[This message has been edited by A027298 (edited 01-18-2003).]

StefanB
01-19-2003, 05:31 AM
You may also consider to use OpenGL's
selection buffer, using only
one 'name' for the entire scene.

The hit record then gives you the min/max
depth value which can be un-projected
to give you the values for the near/far plane.

This requieres an inital guess for the
near/far settings in order to include
all relevant vertices.

See man page for glSelectBuffer.

JustHanging
01-19-2003, 07:33 AM
This wouldn't be for shadow maps by any change, would it? Even perspective shadow maps, I think they require this in practice.

Selection buffer sounds good, especially if you don't have zillions of polygons. Or how about rendering a low-res version and reading the depths from it. Would the error be too big? You could adjust the result a little to compensate the possible error.

-Ilkka

Jan
01-19-2003, 08:17 AM
Originally posted by JustHanging:
Selection buffer sounds good

???

I hope you guys know that selection is ALWAYS performed in software! Selection seems to add some complicated stuff to be done, therefore some guys thought about dropping the selection-mode in OpenGL 2.0.

I have written a Leveleditor, which uses selection. A level with around 10000 vertices takes several seconds (Athlon 1.3, GF 2 Ti) to render and select an object ONCE, so you wonīt be able to use it in realtime applications, 30 times a second.

I think this discussion is quite strange. Why not calculating the relative distance for all objects (without the square-root) and checking which of the closest vertices is inside the view-frustum? I donīt think this should be a problem.

Jan.

JustHanging
01-19-2003, 08:58 AM
You don't do anything with euclidian distance when adjusting near clip plane. You have to know the point nearest to the image plane that fits the screen. It might even not be any of the original vertice, you would have to do the clipping yourself to get it work.

Two ways to get this distance with opengl are selection (or feedback) buffer, and reading back depth buffer. Selection is remarkably faster of these two if there polycount is low. In this application you don't need to push names or stuff like that, so it should be a little faster than your editor.

-Ilkka

A027298
01-19-2003, 07:23 PM
Originally posted by JustHanging:
This wouldn't be for shadow maps by any change, would it?
Yep, something like that.

Currently I am reading back the depth buffer, which is rather slow. Though I render only to a 128x128 window. So I gonna check this Selection buffer thing and compare it with reading back.

knackered
01-19-2003, 11:12 PM
Originally posted by JustHanging:
You don't do anything with euclidian distance when adjusting near clip plane. You have to know the point nearest to the image plane that fits the screen. It might even not be any of the original vertice, you would have to do the clipping yourself to get it work.

Two ways to get this distance with opengl are selection (or feedback) buffer, and reading back depth buffer. Selection is remarkably faster of these two if there polycount is low. In this application you don't need to push names or stuff like that, so it should be a little faster than your editor.

-Ilkka

why clip when clamping the z would do in this case - he only wants the distance.
This is an insane thread.

A027298
01-20-2003, 12:42 AM
Originally posted by knackered:
...This is an insane thread.
I think my question wasn't insane...so pretty straightforward.

nutball
01-20-2003, 12:52 AM
Originally posted by A027298:
Nutball's idea is much much faster, but it makes only sense for static geometry.
[/B]

No, my suggestion works just fine for non-static geometry. My comment about static geometry was in the context of comparing a tree-based search to the brute force approach.

I'd hazard a guess that building a tree for your vertices would take longer than finding the minimum squared distance for all vertices using the simple arithmetic I proposed. Therefore although searching the tree to find the closest vertex might be quicker, if you add in the overhead of building the tree, that technique overall would (probably!) be slower.

If you had static geometry you could build the tree once and re-use it, and in that case the tree might well be a better method. For a dynamic geometry, the simple brute force approach is quite likely quicker than the tree.

That was what my comment about static geometry was aimed at.

JustHanging
01-20-2003, 01:46 AM
How can clamping z achieve this? Say you're standing on a flat floor looking forward. Now the shortest distance to the image plane in a corresponding image (I assume this is what is really needed) is the distance where the floor intersects the bottom clipping plane. That's where you need the clipping. But then, you only need four clipping planes and only need to calculate the z-coordinates, so it might the fastest approach anyway.

For A027298, finding the optimal near plane seems to be quite expensive. Are you sure you can't solve the precision problems some other way? And don't be afraid to put your scene in some sort of scenegraph, sure you can come up with something unless it's some realtime RIB viewer or something where the geometry can totally change from previous frame.

-Ilkka

knackered
01-20-2003, 04:09 AM
Originally posted by A027298:

Originally posted by knackered:
...This is an insane thread.
I think my question wasn't insane...so pretty straightforward.



Are you kidding me?
Transforming the bloody vertices on the CPU will be far faster than reading back the zbuffer and finding the smallest z value out of it! OpenGL selection?! Are you kidding me?
That's what's insane.

j
01-20-2003, 06:37 AM
I think something that nobody has mentioned yet is that finding the closest vertex to the viewing position to determine the distance to the near clip plane will give incorrect results at times.

For example:




. - Eye Position

0--------------------------------------0
-vertex -vertex


Here you can see that the closest vertices are the ones at the end of the ground plane, so the clipping plane would be set to be way out, meaning that almost all of the ground plane would be culled, and the viewer would see almost nothing. Probably not what is desired.

What you really want to do is calculate the closest distance to any of the triangles that possibly could be in view - a much more complex problem.

j

ScottManDeath
01-20-2003, 07:56 AM
Originally posted by j:
I think something that nobody has mentioned yet is that finding the closest vertex to the viewing position to determine the distance to the near clip plane will give incorrect results at times.

For example:

[CODE]
. - Eye Position

0

Hi

thats what I also mentioned in my threads.

He should calculate the vertex distance to the eye plane using my suggestion without the map (that came into my mind becaus I thought he would need further processing)

Bye
ScottManDeath

j
01-20-2003, 03:44 PM
Well, actually, that still doesn't work. Imagine this situation:




.---------->(View Vector)

0---------------------------0


In this case, the eye plane will be vertical, so the near clip plane will be calculated way out by the far right vertex, which is the closest vertex to the camera. This is definitely not correct.

j

fresh
01-21-2003, 02:11 PM
Transform your view point V into object space. Now for each point P(i), find (V-P(i))^2. The point with the smallest value will be your closest point to your view point. Note that this will also include points which are not in view (ie, behind you).

Without some sort of bounding hierarchy, you're not gonna find anything faster than that.

[This message has been edited by fresh (edited 01-21-2003).]

Leon
01-22-2003, 02:10 AM
Hello there,

I believe that the problem of finding the closest vertex is not the problem you really need to solve.

In order to place your near plane as far forwards as possible you need to ensure that it is closer than the closest pixel you render, not the closest vertex. It is quite possible to have a polygon with one vertex far from you and another behind you, outside of your view frustrum, yet the closest pixel will be closer than the vertex in front of you.

Your low-resolution depth read finds these close pixels, but only to an approximation. In your final high-res render you may find a few pixels even closer.

I hope that helps,

Leon

NordFenris
01-22-2003, 05:12 AM
Sort? That doesn't work unless you transform the vertices to eye space on the CPU!


...or transform the camera position into object space... But I retract my case. Thanks, Tom. http://www.opengl.org/discussion_boards/ubb/smile.gif

A027298
01-22-2003, 04:39 PM
Originally posted by Leon:

Your low-resolution depth read finds these close pixels, but only to an approximation. In your final high-res render you may find a few pixels even closer.

Yes, currently I am doing it like that. Maybe the safest and easiest method to do.

rgpc
01-22-2003, 05:18 PM
How about...

1. (At load time - ie. Only done once) Divide your verts into a number of set units and calc the bounding spheres for these units. (ie. List of bounding spheres, list of indices that map your verts to the spheres)

2. Transform your camera into objects space.

3. Find the closest bounding sphere to the eye plane. If sphere overlaps the eye plane and/or there are spheres behind the eye plane then set the near plane to some preselected distance (because it doesn't really matter where you put it, it's going to clip your geometry).

4. If the sphere does not overlap the eye plane, go through the list of verts and find the nearest one to the eye plane.

I think that's not too difficult, "unsafe", cpu intensive or inaccurate...

jwatte
01-22-2003, 06:32 PM
Presumably, you're finding the closest vertex by doing a dot product between the view vector and (vertex - camera) in world space, so that's still safe.

However, pushing the near clipping plane around is generally just not a great idea. Users will still see Z fighting when they're in situations where there's something close to the camera. It's also QUITE likely that you want to draw geometry that extends behind the camera (such as a wall you're running alongside, or the floor you're standing on) so you'll get a negative "closest" value -- then what you you do?

The best solution I know of is to decide on a near clipping plane distance (say, 0.8) and then make sure you put a collision sphere of at least that size around the camera, so that the camera can't clip through geometry (unless that geometry is lacking collision). This, of course, requires that you have a decent collision system, and don't mind running this on your camera everytime it (or the environment) moves.

rgpc
01-22-2003, 07:16 PM
Originally posted by jwatte:
Presumably, you're finding the closest vertex by doing a dot product between the view vector and (vertex - camera) in world space, so that's still safe.


That'll give you the closest vertex to the the view vector wont it? Rather than to the camera position?

That could be the furtherest point from the camera (if you were looking into the base of a cone).

(Or am I missing something...)

JustHanging
01-23-2003, 12:45 AM
Originally posted by rgpc:
(Or am I missing something...)
Yes, you're all missing something here. It seem like Leon is the only one who's got a hang on what this is about. Read his last mail, it should describe the problem quite clearly.

Oh and knackered, you are right. This thread IS insane... Everybody just keeps telling the same stuff all over again, solving the wrong problem.

-Ilkka