Hardware Assist For Constrained Circle Constructions I: Sequential Problems

Hardware Assist For Constrained Circle Constructions I: Sequential Problems
Ching-Shoei Chiang, C Hoffmann, and Paul Rosen
Computer-Aided Design and Applications, 2010

Abstract

In geometric constraint solving, constructing circles with indeterminate radius is an important sub problem. Such constructions are both sequential, meaning that we seek a circle tangent to three known geometric entities, as well as simultaneous, when several sets of entities, among them variable-radius circles, must be determined together. In Part I, we investigate techniques to solve sequential construction problems of variable-radius circles, analyzing the case when at least one of the constraining entities is a B?©zier curve. We consider first an algebraic solution in which we restrict to Pythagorean hodographs (PH). However, the polynomial degrees become very large, rendering this approach impractical. So, we develop an approach in which the needed computations are assisted by graphics hardware commonly available on PCs and laptops. Here we achieve greater generality, allowing arbitrary curves, greater numerical stability, and extreme speed-ups.

Downloads

Download the Paper Download the BiBTeX

Citation

Ching-Shoei Chiang, C Hoffmann, and Paul Rosen. Hardware Assist For Constrained Circle Constructions I: Sequential Problems. Computer-Aided Design and Applications, 2010.

Bibtex


@article{chiang2010hardware1,
  title = {Hardware Assist for Constrained Circle Constructions I: Sequential Problems},
  author = {Chiang, Ching-Shoei and Hoffmann, C and Rosen, Paul},
  journal = {Computer-Aided Design and Applications},
  volume = {7},
  pages = {17--33},
  year = {2010},
  keywords = {geometric constraint solving, variable-radius circles, cyclographic
maps, PH curves, equation solving, hardware acceleration, GPU},
  abstract = {In geometric constraint solving, constructing circles with indeterminate
    radius is an important sub problem. Such constructions are both sequential, meaning that
    we seek a circle tangent to three known geometric entities, as well as simultaneous,
    when several sets of entities, among them variable-radius circles, must be determined
    together. In Part I, we investigate techniques to solve sequential construction problems
    of variable-radius circles, analyzing the case when at least one of the constraining
    entities is a B?©zier curve. We consider first an algebraic solution in which we
    restrict to Pythagorean hodographs (PH). However, the polynomial degrees become very
    large, rendering this approach impractical. So, we develop an approach in which the
    needed computations are assisted by graphics hardware commonly available on PCs and
    laptops. Here we achieve greater generality, allowing arbitrary curves, greater
    numerical stability, and extreme speed-ups. }
}