Sign in to follow this  
Waaayoff

Regarding performance, reading from depth buffer vs intersection tests?

Recommended Posts

Waaayoff    952
If i want to edit my terrain with a brush and so want to know where the mouse is pointing, what would be faster:

1) Unproject mouse coordinates from depth buffer to obtain exact world coordinates, then walk through the quadtree, doing 2D boundary tests to find all the 'leaves' inside the brush's radius

2) Create a ray and do 3D intersection tests with quadtree to find the leaves, then triangle intersection to find exact point.

Assuming big height maps.. (1024x1024 up to 30k x 30k )

Share this post


Link to post
Share on other sites
MJP    19756
Well the problem with reading the depth buffer is that the CPU will need to sync with GPU, which will cause the CPU to just sit around and wait until the depth buffer is fully rendered and copied back to system memory. Depending on how much GPU work you're doing this can be pretty bad for overall frame time, so [i]in general[/i] if you can do something without reading back GPU data then you'll be better off. Unless you can tolerate latency in which case you can work with GPU data from N frames previous to the current frame, but I don't think that would work for your case.

Share this post


Link to post
Share on other sites
Waaayoff    952
Damn. I liked the first solution.

Is there any other way to select vertices? Because the second option will be slow for large maps..

Thanks

Edit: I thought about tracing a ray along the heightmap, but if i use a linear step that would take forever. If i use different steps i could miss hills or mountains. Edited by Waaayoff

Share this post


Link to post
Share on other sites
Matias Goldberg    9577
Adding to what MJP said:
[quote name='Waaayoff' timestamp='1341173618' post='4954639']
1) Unproject mouse coordinates from depth buffer to obtain exact world coordinates, then walk through the quadtree, doing 2D boundary tests to find all the 'leaves' inside the brush's radius[/quote]
You're also dependent on the Hardware. For example the GeForce 400 series is extremely flawed for read-back and they're VERY slow. There were lots of costumer complaints that their brand new GeForce 480 card was performing worse than a GeForce 7600 when using Maya, Blender, and other CAD software (since they use this method for ray picking)

Quadro cards (and ATI's FireGL) usually perform much better for this.

[quote name='Waaayoff' timestamp='1341173618' post='4954639']
2) Create a ray and do 3D intersection tests with quadtree to find the leaves, then triangle intersection to find exact point.
Assuming big height maps.. (1024x1024 up to 30k x 30k )
[/quote]
[b]Worst case[/b] scenario a ray cast to a 30k x 30k terrain map would need 42.426 tests, considering using brute force only. That's hardly "slow" for a decent CPU.
Not to mention you can split that into multiple threads, and use several algorithms (like quadtrees or a simple grid) to speed up computations. And if you know the maximum and minimum altitude of each quadrant before hand, speed up even more.

Method 2 is by far the best one, since you are in full control of the ray picking algorithm and if done well, can perform blazing fast. Of course, it requires more math knowledge, coding time, and/or some google digging. Method 1 is an easy route for the lazy ones.

Note modelling applications use method 1 because they're not in control of what you're raypicking against and that method is very usable for general cases. The mesh being selected could be concave with zillions of triangles. In your particular case, you are raypicking against a Terrain based on a Heighmap. That's a highly researched topic and optimized to death. Edited by Matias Goldberg

Share this post


Link to post
Share on other sites
Waaayoff    952
Ok. I have a question though, how does knowing the maximum and minimum altitude of a quadtree cell speed up things?

Share this post


Link to post
Share on other sites
Matias Goldberg    9577
By knowing the max & min altitude you can get the volume of your quadrant. If the ray cast doesn't hit the entire cube, you can skip all the pixels in it (it's like a regular AABB).
You can do it without knowing the altitude or using a reasonable large value, but you risk the possibility the ray may skip a quadrant when it shouldn't if there's a really, really big mountain (or deep hole) bigger than that "guessed" value (and if the value is way higher than the real value, you lose optimization opportunities)

Share this post


Link to post
Share on other sites
MJP    19756
Like Matias mentioned, ray-casting a heightfield is a thoroughly researched problem. I believe the seminal paper on the subject is "Photo-Realistic Imaging of Digital Terrains", from 1993.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this