class XDag in Tinman.Terrain.Kernel

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

static class

XDag

Remarks

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

Ancestor vertex.

public constant	A = 2
type	int32

G

Grand parent vertex.

public constant	G = 3
type	int32

L

Left parent vertex.

public constant	L = 0
type	int32

LL

Left anchor, left branch child vertex.

public constant	LL = 0
type	int32

LR

Left anchor, right branch child vertex.

public constant	LR = 1
type	int32

Null

Special value used to mark empty vertex references.

public constant	Null = -2
type	int32

R

Right parent vertex.

public constant	R = 1
type	int32

RL

Right anchor, left branch child vertex.

public constant	RL = 2
type	int32

RR

Right anchor, right branch child vertex.

public constant	RR = 3
type	int32

Void

Special value used to mark blocked vertex references.

public constant	Void = -1
type	int32