XDag

Description

static class Tinman.Terrain.Kernel.XDag

Defines constants used to implement the core data structure used to build continuous level of detail meshes.

The following figure illustrated the longest-edge bisection scheme and the associated semantic:

           C
           +
          /.\
         / . \
        /  .  \
       /   .   \
    L /    .    \ R
     /\    .    /\
    /  \   .   /  \
   /    \  .  /    \
  /      \ . /      \
 /        \./        \
+----------o----------+
A          D          B

A triangle ABC with a right angle at C is divided into two smaller child triangles CAD (left child) and BCD (right child) by subdividing its longest edge AB in the midpoint, yielding the point D. Every such subdivision edge (e.g. DL resp. DR in the above figure) is label with semantic tags: anchor and branch. The branch depicts whether the left (L) or right (R) child triangle (CAD resp. BCD) of the parent triangle (ABC) is split by the edge. The anchor of an edge (DL resp. DR) is then defined as the branch of the parent edge (CD).

Using the above spatial interpretation, an edge can have one of the following semantic tags: LL, LR, RL and RR (anchor and branch). Each edge has a defined direction (from right angle corner point to subdivision point, i.e. C to D in the figure), and can be interpreted as a parent-child link. This way, each point has four possible children and two possible parents (this actually yields a directed acyclic graph - DAG).

Two triangles that share their longest-edge form a diamond. Whenever a triangle is split, its neighbour triangle must be split too in order to avoid T-junctions in the resulting mesh. By applying the above semantics, the following diamond types result:

          Diamond                   Diamond (even)              Diamond (odd)

             A                            A                            A
             +                            +                            +
            /.\                          /.\                          /.\
           / . \                        / . \                        / . \
          /  .  \                      /  .  \                      /  .  \
         /   .   \                    /   .   \                    /   .   \
      LR/    .    \RL              LR/    .    \RL              LR/    .    \RL
       /\    .    /\                /\    .    /\                /\    .    /\
      / [LR] . [RL] \              / [LR] . [RL] \              / [LR] . [RL] \
     /    \  .  /    \            /    \  .  /    \            /    \  .  /    \
    /      \ . /      \          /      \ . /      \          /      \ . /      \
   /        \./        \        /        \./        \        /        \./        \
L +-----[?L]-V-[?R]-----+ R  L +-----[LL]-V-[RR]-----+ R  L +-----[RL]-V-[LR]-----+ R
   \        /.\        /        \        /.\        /        \        /.\        /
   [??]    / . \    [??]        [?L]    / . \    [?R]        [?R]    / . \    [?L]
     \    /  .  \    /            \    /  .  \    /            \    /  .  \    /
      \ [LL] . [RR] /              \ [LL] . [RR] /              \ [LL] . [RR] /
       \/    .    \/                \/    .    \/                \/    .    \/
      LL\    .    /RR              LL\    .    /RR              LL\    .    /RR
         \   .   /                    \   .   /                    \   .   /
          \  .  /                      \ [??]/                      \  .  /
           \ . /                        \ . /                        \ . /
            \./                          \./                          \./
             G                            G                            G

[LL] := Left anchor left branch, written next to child.
[LR] := Left anchor right branch, written next to child.
[RL] := Right anchor left branch, written next to child.
[RR] := Right anchor right branch, written next to child.

The following list summarizes the existing edge semantics:

  • Left anchor left branch child (LL) := Edge resulting from subdividing left twice

  • Left anchor right branch child (LR) := Edge resulting from subdividing left, then right

  • Right anchor left branch child (RL) := Edge resulting from subdividing right, then left

  • Right anchor right branch child (RR) := Edge resulting from subdividing right twice

Symmetric child-parent links are represented with the following semantic:

  • Left parent (L) := Parent vertex of a LL or RL edge.

  • Right parent (R) := Parent vertex of a LR or RR edge.

  • Grand parent (G) := Common grand parent of a vertex.

  • Ancestor (A) := The diamond vertex opposite to the grand parent.

Public / Constants

A


public constant A → (2:int32)

Ancestor vertex.

G


public constant G → (3:int32)

Grand parent vertex.

L


public constant L → (0:int32)

Left parent vertex.

LL


public constant LL → (0:int32)

Left anchor, left branch child vertex.

LR


public constant LR → (1:int32)

Left anchor, right branch child vertex.

Null


public constant Null → (-2:int32)

Special value used to mark empty vertex references.

R


public constant R → (1:int32)

Right parent vertex.

RL


public constant RL → (2:int32)

Right anchor, left branch child vertex.

RR


public constant RR → (3:int32)

Right anchor, right branch child vertex.

Void


public constant Void → (-1:int32)

Special value used to mark blocked vertex references.