JBT stands for Jungle BlobTree, the purpose for the project is to replace the existing BlobTree implementation (csoft). The reasons for re-implementing the BlobTree data structure are as follows:
The goal of JBT is to fix all of these problems with a new data structure design and a different BlobTree algorithm. Particular emphasis is to fixing item 1. We would like to reduce the number of field function evaluations to the minimum necessary. Before describing the new data structure to allow these improvements I want to justify these deficiency claims before discussing the details of jbt.
In csoft all implicit surface information (like field value, gradient, colours etc.) are accessed through one function (namely, csoft_object::get_values). The rationale is that to compute all of these other bits of information one must have the field value. To be more efficient the original design of csoft forced the user to query the implicit surface for all types of information. Unfortunately there are flaws with this method. Firstly the get_values function only retrieves a type of information if required, (if a pointer is not passed for the normal, then the normal is not calculated). This causes undue numbers of field function evaluations due to the user not knowing beforehand what pieces of information are required. For instance in polygonization, many calls to the field function are made, but few of those require calls are for points that end up as vertices, to find the normal and the colour for a vertex will result in another call. This causes recomputation of the field function. The second flaw with get_values is that it is extremely cumbersome. Currently there are eight parameters to it, I would like to add another (uv coordinate, but it is too messy). We have huge functions scattered throughout the library calculating all of these eight parameters which has caused the library to grow into a maintenance problem. jbt will contain a caching algorithm for querying the surface information, this can allow repeated calls to the field function while only actually computing it once.
Two of the other points (2 & 5) regarded the definition of attributes for the skeletal primitives in csoft. In csoft there is a global attribute table csoft_attribs::tattribs, this causes extreme difficulties in maintaining two implicit surfaces. The table can grow quite large with multiple implicit surfaces, it is difficult to know when the attribute table should be destroyed, and it is possible that a substantial portion of the table is not being used. Every csoft primitive has a table of its own which is the same size as the largest entry in the global table for an attribute which is defined for the primitive. This is an extremely wasteful design. The reason for the design is the table is required when building the interpolations of attributes through the traversal. This problem is solved in jbt by introducing a new node type into the tree, a non-geometric node. This type of node which is a unary node will contain information that is true for all primitives below the node, (unless usurped by a lower node). The interpolation of like attributes through the tree is trivial using OO design.
A nice side-effect of the introduction of the non-geometric node is that it makes sense to derive not only the attribute types from it but the transformation type as well. Besides just making sense it makes the code in the implicit surface classes much simpler, the computations are always in object space.
Point number six is particularly scathing. It's not a nice
thing to say about a library that has served us very well. Here
is the prime example of the flaws in the OO design. Both warp
and csg data types inherit from the same class that performs
blending. For both of these types this is just plain wrong.
The whole point of csg is not to do blending. However if we
consider warp for a second, it shouldn't even inherit from a
class that produces a scalar field - it just messes around with
the scalar field of other \e BlobTrees. So I propose that it
makes more sense for the warp object to be a sub class of the
afore mentioned unary non-geometric node. When a warp class is
asked for the field value at a point all it needs to do is warp
the point (or inverse warp - but that's another story). A warp
is essentially identical to a transformation - it just isn't an
affine transformation. So the point is that
csoft_object shouldn't be the root of the
heirarchy, it should inherit from csoft_blobtree
which only defines query functions, which are possibly trivially
ignored in csoft_ngnode (non-geometrical node).
From which csoft_warp,
csoft_transform, csoft_attributenode,
and csoft_texture all inherit.
The outline of how I think csoft should have been
designed is that way because that is how I have designed
jbt. The class hierarchy for jbt is
available here. Briefly the
structure of the hierarchy for a BlobTree is as
follows.
jbt_blobtree.
This class declares the necessary virtual functions for
querying information from a BlobTree and caching
the answers.jbt_blobtree: jbt_object which
declares the abstract interface for nodes that contribute to
the scalar field, and jbt_ngnode which declares
constructs for non-geometrical nodes and implements trivial
implicit query functions.jbt_object are either
compound objects (jbt_compound), or they are
primitives (jbt_primitive). A compound object is
the jbt_blend implements super-elliptic blending,
and jbt_csg implements union, intersection and
difference. A primitive object defines a skeleton and produces
a scalar field around it. [At some point in the future a
jbt_rfunction class heirarchy should be derived
from jbt_object.]jbt_ngnode
include jbt_warp, jbt_transform,
jbt_attributenode, and
jbt_texture. Each of these classes implement
only a sub-set of the implicit surface query functions,
namely those which are relevant to it. For instance
jbt_transform implements normal so
that after its child computes the normal, it can transform it
into world space, but it does not implement the
attribute function. Similarly the
jbt_attributenode class implements
attribute but does not implement
normal.
The class hierarchy for a BlobTree is not the only
hierarchy in the library. There are (at present) two others.
The hierarchy for defining attributes, and the hierarchy for
defining field functions (essentially the same thing as the
csoft_blend classes).
The attribute hierarchy represents possibly the greatest advance
over csoft. It implements a completely general
abstraction of the notion of an attribute and (together with the
jbt_attributenode) removes all
specific definition of attributes from the primitives. It
allows the construction of linear combinations of attributes
without costly malloc's of arrays. Placing an
attribute at any point in a BlobTree causes the
attribute to be associated with every primitive in its sub tree,
unless it is usurped by another attribute of the same type. The
one flaw with jbt_attribute is that it relies on a
virtual function which returns a type number. This type number
must be hard coded with every class. This can cause fatal
crashes if two completely different types of classes return the
same value. We could get around this by some automatic
registration of a type number for a class using rtti. I have
chosen not to use rtti because it can be slow, causes code to
bloat, and the standard is not uniformly supported across all
compilers. Future work could definitely focus on some automatic
registration of a type number for a class type.
The field function hierarchy is lifted straight from the
csoft_blend hierarchy. I changed the name because these
classes don't implement blending, they define the field around a
skeleton. Thus they are field functions, not blend
functions. (I believe that these functions have historically
been mistakenly called blend functions, in point of fact, a
blending function is summation, or super-elliptic blending, or
an R-Function). An instance implements a function that takes the
There is not too much to say here. It is essentially unchanged
from what is described in Wyvill, Guy & Galin. The main
difference is to deal with the introduction of the
jbt_ngnode, and in particular the method for
building linear interpolations for the jbt_attribute
classes.
If an implicit surface query is made (like field value, normal,
gradient etc.) the default behaviour in jbt_ngnode
is to ignore it and use its sub-tree's response as its own
reponse. Each of the sub-classes of jbt_ngnode
need to respond to the appropriate queries which are relevant to
it. This has been stated before. When a node is a
jbt_attributenode it needs to override the
attribute function. What it does is sets the
attribute passed to answer the query with (see the definition of
jbt_blobtree::attribute) if the coefficient for the
current term in the linear combination is non-zero. Every
instance of jbt_attribute keeps a coefficient to
use for successive terms. This coefficient starts off as zero,
when an attribute node is traversed it first traverses the child
and then it adds itself scaled by the coefficient and sets the
coefficient to zero. That way the attribute in the tree which
is closest to a leaf is the attribute used for that leaf. The
next problem is what to do in blending nodes. A blend node
traverses each of its children in turn, setting the coefficient
for each of those traversals to the field value of the child
(scaled by the inverse of the level surface). It also sums up
the coefficients that were left after each of the traversals.
If there existed a jbt_attributenode in the
traversal then the coefficient will have been set to zero, if
not it is still the field value of the child. This sum is used
as the new coefficient when leaving the
jbt_blend::attribute call. That way
jbt_attributenodes above the blend in the tree will
use that sum as their coefficient effectively sowing their value
onto the traversals of the blend which do not include a
jbt_attributenode. I know that all must sound
incredibly confusing. But that is not because the algorithm is
complex, it is I think because of the nature of tree
traversals. It is hard to describe something which is bushily
recursive in a linear way - like language. All of the functions
which implement this are under 5 lines long. There is
very little code involved.
At the time of this writing, Jan 12 '99, most of what has been
mentioned has been implemented. I have been visualizing the
tree by using the Bloomenthal polygonizer from Graphics Gems
IV. What has not is the warp classes, and the R-Function
classes. The reason is I wish to be seriously careful with the
warp classes and really study their implementation in
csoft so that we can possibly avoid the numerical
problems that they have on the Alphas. Also not implemented is
the texturing algorithms. These should be quite easy for me to
add in.
I am extremely excited about the new tree, it works quite
well. And it is obviously fast given its caching mechanism. The
caching needs to be improved though. Currently it can only
cache for one point at a time, you do this by calling
jbt_blobtree::beginQuery. It would be very nice to
also be able to save a cache in some structure which can be
consulted again in the future. This would essentially create a
copy of the tree storing the cached data at each geometric
node. If that cache was needed again, it could fill the tree
with its data and more queries could be made. It would be
expensive to make these copies of the tree however. But in the
end, if you knew you would need the cached data it would be much
cheaper.
Of course a great amount of work remains to implement
polygonization of the tree. Or at least adapting
psoft to that task. And also visualization using
ray-tracing needs to be written as well. I plan to look very
hard at the Sherstyuk algorithm from Implicit Surfaces '98. My
initial guess is that it won't be suitable for the
BlobTree because of warping, but I want to make sure.
Otherwise I will look at affine arithmetic. Luiz Henrique at
IMPA mentioned a student who wanted to implement an affine
arithmetic ray intersection algorithm for csoft. I
will be consulting with him to see if it could be done for
jbt instead.