A Hierarchical Representation and Computation Scheme of Arbitrary-dimensional Geometrical Primitives Based on CGA

作者：Luo, Wen; Hu, Yong; Yu, Zhaoyuan^*; Yuan, Linwang; Lu, Guonian

来源：Advances in Applied Clifford Algebras, 2017, 27(3): 1977-1995.

DOI：10.1007/s00006-016-0697-3

• Data structure
• Geometric algebra
• Geometric computing
• Topological relations
• Triangle intersection

Resolving the conflicts between the high dimensionality of geometry representation and the linear organization and storage of geometrical objects in computer memories plays a key role in spatial data structure constructions. In this paper, a new data structure MVTree is developed based on geometric algebra to support the unified organization and computation of geometrical primitives. The MVTree is a tree-like data structure which has a dimensional hierarchical structure generated by outer product. Multidimensional geometrical primitives is represented as the combination of blades stored in the nodes of MVTrees. The geometric computation between different geometrical objects is operated with GA operators with a judgement-based hierarchical computation. Applications of the MVTree are demonstrated by a topological relation computation and a Delaunay-TIN intersection. The results suggest that the MVTree structure can support unified representation of arbitrary-dimensional geometrical primitives, and can integrate data organization and computation in a unitary structure as well. The application of the new MVTree data structure can not only reduce the complexity of data architectures but also inherit the power of geometric algebra computing to improve the processing ability of computer graphic software.

• 出版日期2017-9
• 单位南京师范大学