Browse Prior Art Database

Realization of Constructive Solid Geometry Recursively Defined Models With Expansion of Variables/Functions

IP.com Disclosure Number: IPCOM000120414D
Original Publication Date: 1991-Apr-01
Included in the Prior Art Database: 2005-Apr-02
Document File: 4 page(s) / 210K

Publishing Venue

IBM

Related People

Todd, SJ: AUTHOR

Abstract

Two Constructive Solid Geometry (CSG) techniques are disclosed with advantages of storage-economy when realizing complex models, and when generating fractals with indefinite zoom abilities into complex pictures.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 30% of the total text.

Realization of Constructive Solid Geometry Recursively Defined Models
With Expansion of Variables/Functions

      Two Constructive Solid Geometry (CSG) techniques are
disclosed with advantages of storage-economy when realizing complex
models, and when generating fractals with indefinite zoom abilities
into complex pictures.

      The first technique, Lazy Expansion of CSG Variables and
Functions, makes novel use of recursive definitions for solid
objects, with both recursion and recursion-depth handled dynamically
by the renderer.  The second technique, Realization of Recursively
defined CSG Models, is an expansion of CSG programs to CSG trees on
demand during recursive subdivision with removing of expanded partial
programs.  The techniques relate to UKSC graphics work, in particular
to the Winchester Solid Modeller (WINSOM) rendering prototype and the
Extensible Solid Modelling Editor (ESME) language.
LAZY EXPANSION OF CSG VARIABLES AND FUNCTIONS

      Most current CSG rendering systems operate on expanded CSG
trees.  Though the input language permits a more structured
definition, a prepass is used to expand the input into a tree.  As
more complex input languages are used (e.g., ESME as opposed to
WINSOM), the user is encouraged models in which the expanded tree
becomes larger and larger. The proposal is to use delayed (lazy)
expansion of the models to trees.  Where a model references a
submodel by name, current systems make a copy of the model defined
for that name during the expansion phase.  Instead, a reference node
is proposed to be built that contains a pointer to the model for the
name, a transform, initially set to the unit transform and a
backtransform.

      As transformations are applied to the containing object they
are passed down and concatenated to the transform field of the
reference node.  Thus, the expansion phase becomes a partial
expansion phase, in which only transforms are expanded.  During the
preparation phase, the backtransform is evaluated as the inverse of
the transform.  During simplification in the recursive subdivision
phase, these reference nodes are encountered.  The backtransform is
applied to the current voxel to give a transformed voxel, and the
referenced subnode is simplified for the transformed voxel.  The
resulting simplification of the referenced node gives rise to three
cases.
1.  Empty or full, in which case empty or full is returned as the
simplification of the referencing node.  This will be common at the
lower levels of recursive subdivision with small voxels.
2.  The same value as the unsimplified referenced node, in which case
the referencing node is passed back as its own simplification.  This
will be common at the high levels of recursive subdivision, where the
voxel encompasses large parts of the model.
3.  A non-trivial prune yielding a new value, pointing at a pruned
partial copy of the referenced node.  In this case, the new value is
copied into a newly...