5
\$\begingroup\$

I've been experimenting with generating a quad sphere. This sphere subdivides into a quadtree structure. Eventually I'm going to be applying some simplex noise to the vertices of each face to create a terrain like surface.

To solve the issue of cracks I want to be able to apply a geomitmap technique of triangle fanning on the edges of each quad, but in order to know the subdivision level of the adjacent quads I need to identify which quads are adjacent to each other.

Does anyone know any approaches to computing and storing these adjacent quads for quick lookup?

Also It's important that I know which direction they are in so I can easily adjust the correct edge.

enter image description here

\$\endgroup\$
  • 2
    \$\begingroup\$ How are you generating the sphere? It looks like maybe you're taking a cube and subdividing each face into quads. If so, then finding neighbors within each subdivided cube face is trivial since they just form a square array. Then you just have to put in some special-case logic to find neighbors across the 8 original cube edges. \$\endgroup\$ – Nathan Reed Sep 27 '13 at 17:47
  • \$\begingroup\$ @NathanReed thats spot on, its a cube created from 6 quads, each quad gets subdivide. Okay so there isn't a nice mathematic way of considering edges, just going to have to write some special case logic :D \$\endgroup\$ – Caius Eugene Sep 27 '13 at 18:47
2
\$\begingroup\$

It's not a full answer, but it's too long for a comment...

From your question I presume you want to use a LOD system (geomipmap approach) and you're creating your mesh by cube subdivision, so why not to think about a LOD during both stages - mesh creation and rendering?

You start from just a 6 planes, so it's really easy to tell which sides are connected. Then, when you subdivide one of the planes you know which neighbors are at the all 4 edges. You can also store the newly created, internal edges.

This way you can create a hierarchical, tree-like data, where you start from 6 quads and every quad have 4 child quads. Having such data you can easily iterate over all LOD levels. You can even store the mesh data precomputed for all LOD levels, or you can create them on the fly, depending on camera move. There are really many possibilities here, but I can't help you more as I don't know what data are you going to need for your algorithm to work.

\$\endgroup\$
1
\$\begingroup\$

In their paper "Navigating through Triangle Meshes Implemented as Linear Quadtrees", Michael Lee and Hanan Samet propose a method of addressing the nodes (triangles) of a spherical quad-tree such that the "addresses" of neighbouring nodes (triangles) of equal size can be found in constant time.

The underlying principle they use is, that by assigning the two-bit sequences 00, 01, 10 and 11 to the upper, left, center and right subdivision of an up-facing triangle and to the lower, left, center and right subdivision of a down-facing triangle, the address of the right, left or vertical neighbour of any node (triangle) in the quad tree can be expressed by binary operations AND, OR, XOR, NOT and bit shift.

It seems the authors made a copy of their work freely available here: http://www.cs.umd.edu/~hjs/pubs/LeeTODS00.pdf

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.