Entry Cameron:1992:RMG from tog.bib

Last update: Sat Sep 5 02:07:01 MDT 2009                Valid HTML 3.2!

Index sections

Top | Symbols | Numbers | Math | A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z

BibTeX entry

@Article{Cameron:1992:RMG,
  author =       "Stephen Cameron and Yap Chee-Keng",
  title =        "Refinement Methods for Geometric Bounds in
                 Constructive Solid Geometry",
  journal =      j-TOG,
  volume =       "11",
  number =       "1",
  pages =        "12--39",
  month =        jan,
  year =         "1992",
  CODEN =        "ATGRDF",
  ISSN =         "0730-0301",
  bibdate =      "Fri Jan 5 07:58:42 MST 1996",
  URL =          "http://www.acm.org/pubs/toc/Abstracts/0730-0301/123764.html",
  abstract =     "In constructive solid geometry, geometric solids are
                 represented as trees whose leaves are labeled by
                 primitive solids and whose internal nodes are labeled
                 by set-theoretic operations. A {\em bounding function}
                 in this context is an upper or lower estimate on the
                 extent of the constituent sets; such bounds are
                 commonly used to speed up algorithms based on such
                 trees. We introduce the class of {\em totally
                 consistent bounding functions}, which have the
                 desirable properties of allowing surprisingly good
                 bounds to be built quickly. Both outer and inner bounds
                 can be refined using a set of rewrite rules, for which
                 we give some complexity and convergence results. We
                 have implemented the refinement rules for outer bounds
                 within a solid modeling system, where they have proved
                 especially useful for intersection testing in three and
                 four dimensions. Our implementations have used boxes as
                 bounds, but different classes (shapes) of bounds are
                 also explored. The rewrite rules are also applicable to
                 relatively slow, exact operations, which we explore for
                 their theoretical insight, and to general Boolean
                 algebras. Results concerning the relationship between
                 these bounds and active zones are also noted.",
  acknowledgement = ack-nhfb,
  keywords =     "algorithms; design; performance; theory",
  subject =      "{\bf I.3.5}: Computing Methodologies, COMPUTER
                 GRAPHICS, Computational Geometry and Object Modeling,
                 Hierarchy and geometric transformations. {\bf F.2.2}:
                 Theory of Computation, ANALYSIS OF ALGORITHMS AND
                 PROBLEM COMPLEXITY, Nonnumerical Algorithms and
                 Problems, Computations on discrete structures. {\bf
                 F.2.2}: Theory of Computation, ANALYSIS OF ALGORITHMS
                 AND PROBLEM COMPLEXITY, Nonnumerical Algorithms and
                 Problems, Geometrical problems and computations. {\bf
                 I.1.1}: Computing Methodologies, ALGEBRAIC
                 MANIPULATION, Expressions and Their Representation,
                 Simplification of expressions. {\bf J.6}: Computer
                 Applications, COMPUTER-AIDED ENGINEERING,
                 Computer-aided design (CAD).",
}

Related entries