wiki:soc/2007/GenericGeometricLibrary

Version 2 (modified by Huseyin Akcan, 15 years ago) ( diff )

--

Halfedge Data Structure Template Library

0. Introduction

In this project, we will develop a generic halfedge data structure template library. A brief overview of halfedge data structures by Herve Bronnimann is available here (Sections 1-3). In this project, we will follow the same design principle described in the introduction document, with various modifications and additions.

The purpose of this document is to share the design decisions with the Boost community, and receive feedback. Please feel free to comment and discuss possible ideas as all feedback are welcome.


1. Halfedge Data Structure Concepts

We give the concepts of halfedges in the following sections. First we analyze the halfedge data structure traits, which define various choices about the HDS and lets us configure the halfedges. Later we present the Halfedge data structure and design details.


1.0. HDS Traits

We define the HDS traits concept as a class, which provides all the component types for HDS and defines the choices. In this class the choices about the HDS is two folds:

  • The mandatory types: such as the type of the HDS, iterators for halfedges.
  • The optional types: such as enabling facets, enabling vertex types, using extra HDS access methods additional to the mandatory types.

The optional types are added to data structure only if they are explicitly defined, otherwise based on zero overhead principle no storage is assigned for them. In this traits class we discuss the advantages and disadvantages of each choice, including runtime options and storage options.


Figure 1. Halfedge data structure with all available features.

Figure 1 shows all available access methods and pointers for a halfedge data structure. However, not all of these have to be used in order to implement a HDS. Below we define the types in the HDS traits class, and discuss the options.

TypeMandatory or optionalAllocates memoryDefinition
Vertex typeoptionalOnly if definedDefines the type of vertex stored in the HDS.
Vertex handleoptionalOnly if definedDefined only if vertex type is defined. Defines an iterator to access vertices.
Vertex const handleoptionalOnly if definedSame as vertex handle, only iterator is defined as non mutable.
Halfedge typemandatoryyes, based on #of types usedDefines the type of the halfedges stored in HDS (such as forward, backward, bidirectional etc.).
Halfedge handlemandatoryyes, based on #of types usedDefines an iterator to access halfedges, based on halfedge type.
Halfedge const handlemandatoryyes, based on #of types usedSame as halfedge handle, only non mutable.
Facet typeoptionalOnly if definedDefines the type of the facet.
Facet handleoptionalOnly if definedDefined if only facet type is also defined. Defines an iterator to access facets.
Facet const handleoptionalOnly if definedSame as facet handle, only non mutable.
Hole typeoptionalOnly if definedRequires facets are defined. By default we assume HDS has no holes. If set means that HDS supports holes.
Hole handleoptionalOnly if definedRequires Hole type defined. Defines an iterator to access holes in a facet.
Hole const handleoptionalOnly if definedSame as hole handle, only non mutable.

HDS types and basic operations are defined as:

  • Forward_hds: Defines that the rotations around vertices are clockwise and rotation around facets are counter clockwise. Requires at least one of next_at_facet(), next_at_source(), next_at_target() halfedge operations are implemented.
  • Backwards_hds: Defines that the rotations around vertices are counter clockwise and rotation around facets are clockwise. Requires at least one of prev_at_facet(), prev_at_source(), prev_at_target() halfedge operations are implemented.
  • Bidirectional_hds: Defines that rotations can be on both directions for both vertices and facets. Requires that at least one operation from forward_hds and backward_hds each is defined.

1.1. Halfedge Data Structure

This class provides the halfedges, access to halfedges, operations on halfedges based on the configuration done using the traits. HDS class has the following operations:

NameDefinition
create new edgeCreates two halfedges, as halfedges are required to be created by their opposite.
delete edgeDeletes a halfedge and its opposite
opposite edgeGets the opposite edge of the given halfedge
Default constructorCreate an empty HDS.
copy constructorTo create a new HDS.
Halfedge containerGrant access to the container.
Euler operationsVarious Euler operations on the HDS. This contains multiple methods.

2. Algorithms

A set of algorithms on entities obeying the defined concepts (in the intrusive fashion). More details coming soon.


3. Implementation details

An homemade implementation of the concepts (various HDS) as well as adapters for Leda and CGAL. More details coming soon.


4. Examples

Examples using halfedge data structures for Voronoi / Meshing and for 2D Polygonal Modeling. More details coming soon.

Note: See TracWiki for help on using the wiki.