Jump to content
  • Advertisement

Archived

This topic is now archived and is closed to further replies.

cheese

How could SOAR be adapted for planet rendering?

This topic is 5154 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

My intention for this thread was to discuss how SOAR could be adapted for spherical terrain, to represent planetary objects. To me, it seemed that gamedev threads relating to SOAR were never particularly successful, and my threads seem to be made of lead, but what the hell. For those that aren''t familiar with SOAR, its an engine that implements the ''Visualization of Large Terrain made Easy'' approach, by Lindstrom and Pascucci. It was intended for flat, tiled terrain. I was hoping to adapt the approach to spherical terrain, much like ROAM has been (for example). For now, I''ll assume that everyone is familiar with the approach. If anyone wishes, I can try to explain it as I understand it (which of course may not be entirely accurate). I''ll briefly describe some of the problems I can think of. The use of a tree of vertices rather than triangles means that cracks can never appear in the mesh, and therefore neighbours to adjacent nodes in the mesh are not necessary. However, this could be a problem for representing continuous meshes such as a planet. As a binary tree of vertices is used, a cube would seem the best base shape to use. As tree nodes do not include pointers to neighbours, I had thought of treating each face of the base cube as a seperate flat terrain. However, this would cause problems along the edges the cube faces, and would mean that vertices could not be shared along these edges. For a single tile of terrain, SOAR generates a single triangle strip to be rendered. For 6 faces of a cube, this would generate 6 triangle strips. Multiple rendering calls (ie. DrawIndexedPrimitive) is undesirable, but as no more than 3 faces can ever face the viewer at the same time, a maximum of 3 calls should be acceptable. It should also be possible to use share a single vertex buffer among each of the 6 faces. For now that should be enough to start a discussion if anyone is interested. I have more points, though at this stage, would anyone actually be interested in contributing to this thread?

Share this post


Link to post
Share on other sites
Advertisement
I don't really know exactly how SOAR works (haven't got the chance to read the paper yet, but in principle, any "flat" terrain LOD can be adapted for planet rendering by starting from a cube, and making some adjustments as were done in the case of ROAM. Although I personally prefer a system that was designed for planet rendering from the start (as indicated by my planet rendering threads), the above statement still holds, and my reply below are based on that.

quote:
Original post by cheese
The use of a tree of vertices rather than triangles means that cracks can never appear in the mesh, and therefore neighbours to adjacent nodes in the mesh are not necessary. However, this could be a problem for representing continuous meshes such as a planet.

If I understand correctly, the problem arises because at least some of the leaf-node vertices are considered to be on the edge of the mesh? If so, a possible solution is this: use a directed graph rather than a tree. Each vertex would then be able to have more than one parent vertex. Then you can start from whatever arbitrary vertex, building the graph as you move around the mesh, until you finally reach the vertex on the oppsite side. Your graph would then look something like this:

_x_
| |
x x
| | | |
x x x x
| | | |
x x
|_ _|
x

Instead of:

_x_
| |
x x
| | | |
x x x x
...

EDIT: Here - maybe this time the ascii wouldn't screw up...

Btw, since you don't ever render the entire planet (at most, you would render half of it), the mesh may not have to be closed at all, so you maay be able to stick with the original representation.
quote:
As a binary tree of vertices is used, a cube would seem the best base shape to use. As tree nodes do not include pointers to neighbours, I had thought of treating each face of the base cube as a seperate flat terrain. However, this would cause problems along the edges the cube faces, and would mean that vertices could not be shared along these edges.

As long as you somehow do keep track of neighbor vertices, at least along the edges of the cube's faces, you should be able to make sure that the edges match.

Michael K.,
Co-designer and Graphics Programmer of "The Keepers"



We come in peace... surrender or die!

[edited by - technobot on June 9, 2004 5:37:57 PM]

Share this post


Link to post
Share on other sites
Check out: http://www.zenerd.com/zengeneral/code.html

for Terrain Paging; I use SOAR under six faces for a nice effect.

For planet rendering, you need a mapping between a sphere and planes which can be done via cube subdivision.

Share this post


Link to post
Share on other sites
technobot:

I told you my understanding of SOAR was probably not entirely accurate you are quite right, the approach itself does infact use a directed acyclic-graph of vertices rather than a tree.

As I understand it, the system described in your planet threads is not limited to any resolution. Say that my planet is limited to a certain resolution, and therefore I can determine the size of the mesh at its highest resolution (even if it is very hundreds or thousands of megabytes).

Say that I was using the system described in your planet threads, and wanted to store the following nodes on disk:



I would do it in the standard array format of {1, 2, 3, 4, 5, 6...}, and store the nodes like this in a file. Admittedly it'd probably be inefficient in terms of storage, but hopefully the performance should justify it. Using a file mapping approach as used in SOAR, the Operating System would page nodes to and from disk as necessary. By storing the nodes contiguously as described above, nodes at the same resolution would be stored close together on disk, and therefore should minimise the number of page faults.


ZenGeneral -

Many thanks, how difficult is it to implement multiple paging (ie. as you do, for 6 faces). I assume there is more to it than simply mapping memory to 6 seperate files, each for a different face? I don't suppose you were ever thinking of releasing your Terrain Paging project were you ?

[edited by - cheese on June 9, 2004 6:38:50 PM]

Share this post


Link to post
Share on other sites
> The use of a tree of vertices rather than triangles means that cracks can never appear in the mesh

This is not fairly true ; with triangles tree you can also prevent cracks, and using only tree of vertices won''t prevent cracks if you dont have the correct algorithm

In my case, I decided to store neightboor informations. This allow to compare current patch/chunk/triangle to neightboors ones and to force neightboor ones when needed.

> Multiple rendering calls (ie. DrawIndexedPrimitive) is undesirable
> It should also be possible to use share a single vertex buffer among each of the 6 faces

I think it''s mainly a compromise to find. In the case of chunks, it''s quite reasonable to use a vertex buffer for each chunk. Think that using vertex buffers is always better than no vertex buffers.
Another thing is that you''ll have troubles with verteces that are shared among many chunks.

In my case, I use a cube (12 triangles) that is tesselated 3 or 4 times : this gives me all the chunks (12*4*4*4 -> 768 chuncks). If you''re intersted I can try to explain the solution I found for paging, but it''s a bit complexe.

Share this post


Link to post
Share on other sites
MV -
quote:
This allow to compare current patch/chunk/triangle...


So am I right in assuming you used a tree of triangles rather than vertices? It seems that you'd need to maintain neighbour pointers regardless of whether you used a tree/DAG of triangles or vertices.

quote:
think it's mainly a compromise to find. In the case of chunks, it's quite reasonable to use a vertex buffer for each chunk


The reason that I suggested a single, shared vertex buffer was because it is very costly to switch vertex buffers every frame. Do you mean that you have a vertex buffer for each chunk, and then copy the contents of these buffers into a single vertex buffer in virtual memory each frame?

quote:
If you're intersted I can try to explain the solution I found for paging, but it's a bit complexe.


If you wouldn't mind I would be very interested in your solution for paging. If I used a triangle tree, I was wondering if it would be possible to use file mapping to page both triangles and vertices during run time.

[edited by - cheese on June 10, 2004 7:34:27 AM]

Share this post


Link to post
Share on other sites
SOAR & Spherical Terrain Rendering - wow was just going to ask this too

Share this post


Link to post
Share on other sites
quote:
So am I right in assuming you used a tree of triangles rather than vertices? It seems that you''d need to maintain neighbour pointers regardless of whether you used a tree/DAG of triangles or vertices.


Maybe I''m bit confused ... but, using your terms, it looks like I use a tree of triangles. Actually create a terrain engine on a vertexe DAG is not a good idea if you plan to use paging... How could I explain ? It''s all about neightbooring. The avantage of using triangles trees (for me, a triangle tree is a chunck is that neightboor''s informations need to be stored at the lower level, they can be created on-the-fly for LoD high level

quote:
The reason that I suggested a single, shared vertex buffer was because it is very costly to switch vertex buffers every frame. Do you mean that you have a vertex buffer for each chunk, and then copy the contents of these buffers into a single vertex buffer in virtual memory each frame?


Actually I''m not yet at this stage (still rendering verteces and lines !!! ). I''m not an expert in vertex buffers so I can be wrong, but as I already wrote, many vertex buffers seem better than no one (no ?)

quote:
I would be very interested in your solution for paging.

quote:
to use file mapping

I recognize "file mapping" from the Lindstrom article, but I actually dont know what it precisely is. I use a file in binary mode.

As I wrote in previous post, at the end of the tesselation step, I have 768 chuncks. Then each chunk is tesselated so that it contains 192 verteces. The file storing all the data is composed of two part :
- first part contains a summary of all chunks : only the 3 vertices of the LoD 0 triangles and its neightbooring (and index is enougth) informations. It''s a kind of table of content
- second part contains for each chunck all the vertices (normals also planned)

At the beginning of the programm the first part is all loaded, I use it to determine which chunks are in the camera scope and to load them when needed. Loading is done via a binary file, maybe not the better solution, it works ! (quite fine actually)

To finish, I plan to build the triangles tree on the fly (easy it''s a kind of pattern using the vertexe indices)
Another point ; there''s a trouble with vertex shared between several chunks ; they exist in each chunk so for dynamically transform the terrain, for such vertex I should deal with a vertex list which complicates the access function.

A lot of concepts are still "under construction" because I''m working since a lot of months on the edition functionnalties.
Hope this was clear.

Share this post


Link to post
Share on other sites
I’ve just got the terrain rendering bug again and have started on/off work on a DirectX version of SOAR. It won’t be spherical at this stage. I’ll give you a few details: In order to save on disk space, my implementation will only store only elevation values, not explicit vertex locations, these are calculated along with the texture coordinates at the mesh refinement stage. It will also templatised, so that at compile time I can choose any standard type for my elevation values, __int8, __int16 or float etc. The data requirement per vertex will be 9, 10, or 12 bytes, instead of 20. Doing this may be slower during the refinement stage, but also may not be if it reduces page faults.

As for spherical rendering, you’ve already suggested using a cube, that’s what I may do because finding an indexing scheme based on sphere may be difficult. Most planetary textures and terrain data are based on simple cylindrical projection, so you’ll have to find, or write your own software, which will generate the six faces in cube projection. Let me know if you find any software that does this. You could also use 3D Perlin noise to create textures and elevation values.

Fixing the cracks between cube faces. You won’t need to make any special arrangements in your MeshRefine() function to fix these. The cracks are fixed off-line, in the pre-processing phase of your terrain data. Don’t ask me the details, because I don’t know, but you’ll need to make sure that the sphere hierarchy in each face takes into account its neighbours.

A final note, someone said they didn’t know what file mapping was. File mapping makes a huge file, a file that does not fit in main-memory, appear to the programmer as a being simple array, despite much of the file remaining on disk. The operating system will page in parts of the file, as required. In the case of terrain rendering, in order to minimise the number of page faults, it is up to the programmer to utilise some clever form of indexing which reflects the vertex access pattern during mesh refinement, such as interleaved-quad-trees (66% disk space overhead), embedded-quad-trees (33% disk space overhead) or hierarchical-pi-order-curve (no overhead).

Regards,

Justin.

Share this post


Link to post
Share on other sites
Hahaha, this is actually kinda funny.

The answer to this question is the reason why SOAR is such a good algorithm. What it really does is take a Triangle and subdivide it appropriately into a triangle strip. In this way, you can build any object built out of triangles (by continuing the strip with a recursive call to the same algorithm). A sphere tesselation coupled with the SOAR algorithm (and perhaps an octree-like system of distance culling for the large data set) could render a planet at extraodinary rates and exquisite detail.

For these reasons, I too am currently working on a SOAR implementation.

Share this post


Link to post
Share on other sites

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!