Advanced programming and future developments

Trees and recursion

SvLis is highly recursive. Its three major data structures--primitives, sets, and models--are all organized as trees, and the usual way of programming with them is to use recursive functions to walk those trees. As examples, I'll describe two of svLis' internal functions: one that performs a membership test to classify a point against a model (in fact in svLis this is a member function of the class sv_model, but it's shown below as a simple function for clarity), and another that computes the range of potential values generated by a set within a particular box, using maxima and minima instead of intersection and union (this function is actually a member of the sv_set class, and was discussed on Page

The purpose of these examples is to show you how to go about programming your own functions using svLis. Note in particular that the first example need not be a friend of any of the classes it uses--the accessing functions built into the classes to return such things as the two child operands of a set-theoretic operator are sufficiently rich to allow any possible function to be programmed. The only private data in the classes are for housekeeping--things such as reference counts for items pointed to and so on--and are, in a sense, not part of the svLis geometric modeller at all, but merely necessary adjuncts to allow efficient storage management, reliable and compact input and output, and so on.

Membership test for a point

It is of course possible to perform a membership test to classify a point against a model without dividing it. First a check would be done that the point was in the model's box. If not, then a conventional code for air would be returned as the result. If the point were in the box, it would be tested against each set in the model's list of sets. If the point was found to be in any set, a code indicating solid would be returned (the list is regarded as being unioned for the purpose of membership testing). Failing that, if the point was found to be on the surface of a set, a code for surface would be returned; otherwise the result would be a code for air.

However, for complicated sets this would be a very inefficient process, especially if a large number of points were to be tested . It is much better to divide the model first (for example using the naïve decision procedure dumb_decision(...); see Page ). Then, svLis performs a recursive traversal of the tree of model boxes until the leaf box containing the point to be tested is found; and that point is tested against the simple pruned list of sets in that leaf model. This is how the membership test function works:

// Membership test a point against a model.

mem_test member(const sv_model& m, const sv_point& p,
                sv_primitive known_surface[])
{
  mem_test result = SV_AIR;
  mem_test temp = SV_AIR;
  sv_set_list sl;

// Is the point in the model's box?

  if(m.box().member(p) == SV_AIR) return(SV_AIR);

// If m is a leaf, check against each set in the leaf's
// list.  Otherwise walk down the model tree.

  switch (m.kind())
  {
  case LEAF_M:
    sl = m.set_list();
    while(sl.exists())
    {
      temp = sl.set().member(p, known_surface));
      if (temp == SV_SOLID) return(SV_SOLID);
      if (temp == SV_SURFACE) result = SV_SURFACE;
      sl = sl.next();
    }
    return(result);

  case X_DIV:
    if (p.x < m.coord())
      return(m.child_1().member(p,known_surface));
    else
      return(m.child_2().member(p,known_surface));

  case Y_DIV:
    if (p.y < m.coord())
      return(m.child_1().member(p,known_surface));
    else
      return(m.child_2().member(p,known_surface));

  case Z_DIV:
    if (p.z < m.coord())
      return(m.child_1().member(p,known_surface));
    else
      return(m.child_2().member(p,known_surface));

  default:
    svlis_error("member(sv_model, ...)",
      "dud model kind", SV_CORRUPT);
  }

// Should never get here.

  svlis_error("member(sv_model, ...)",
      "error in model; returning SV_AIR",SV_CORRUPT);
  return(SV_AIR);
}

This traverses the model's tree of boxes, comparing the coordinates of the point with the coordinates of the planes that divide any box into its two smaller children and selecting the appropriate child. When a leaf is reached, the membership test is done for all the sets in the list of sets at that leaf. The array of primitives known_surface[ ] allows the user to provide the function with a list of primitives for which the point is known to be on the surface (which would happen, for instance, if the point was at the intersection of the surfaces of three primitives coming together in a corner). This known-surface array makes the membership test more efficient, as it removes the need for the system to categorize the point against the primitives which (in the example) generated it. If known-surface information is not available, just send the function a pointer to an undefined primitive as its third argument, and this will be ignored.

There are a couple of errors at the end of the function which should only be printed if the data structures have been corrupted somehow.

The potential range of a box in a set

As was described on Page

, svLis uses interval arithmetic to make a (conservative) estimate of the range of potential values that a primitive may take in a box. The maximum and minimum of a pair of intervals are themselves well-defined intervals

. The equivalences between maximum and intersection and minimum and union can be exploited to give the range of potentials that a set can exhibit in a box. To compute this, the function recursively traverses the tree of unions and intersections that represents a set, finds the ranges for the leaf primitives, and combines them. As it does so, it keeps track of the primitives corresponding to the sets which gave rise to the bottom and top of the range interval (the `winning' primitives; these may of course be the same). Here is that function:

// Range for a box (and winning leaf sets).

sv_interval sv_set::range
  (const sv_box& b, sv_set* w_lo, sv_set* w_hi)
{
  sv_interval result_2;
  sv_interval result;
  sv_set w_2_lo, w_2_hi;

  switch (contents())
  {
  case SV_EVERYTHING:
    w_lo = this;
    w_hi = this;
    return(sv_interval(-2.0,-1.0));  // By convention

  case SV_NOTHING:
    w_lo = this;
    w_hi = this;
    return(sv_interval(1.0,2.0));    // By convention

// Leaf set - return corresponding primitive's range
// for box b.

  case 1:
    w_lo = this;
    w_hi = this;
    return(primitive().range(b));

// Compound set - recursively call range for the
// children.

  default: 
    result = child_1().range(b, w_lo, w_hi);
    result_2 = child_2().range(b ,&w_2_lo, &w_2_hi);

    if (operator() == SV_UNION)  // U == minimum
    {
       if (result_2.lo < result.lo)
       {
          *w_lo = w_2_lo;
          result.lo = result_2.lo;
       }
       if (result_2.hi < result.hi)
       {
          *w_hi = w_2_hi;
          result.hi = result_2.hi;
       }
    } else
    { // SV_INTERSECTION == maximum
       if (result_2.lo > result.lo)
       {
          *w_lo = w_2_lo;
          result.lo = result_2.lo;
       }
       if (result_2.hi > result.hi)
       {
          *w_hi = w_2_hi;
          result.hi = result_2.hi;
       }
    }

// Keep track of the attributes.

    if ( this->has_attribute() && ( !(w_lo->has_attribute()) ) )
       *w_lo = w_lo->attribute(this->attribute());
    if ( this->has_attribute() && ( !(w_hi->has_attribute()) ) )
       *w_hi = w_hi->attribute(this->attribute());

    return(result);
  }
}

The function first checks to see if it has been given the universal or the empty set, in which case the answer--following an appropriate convention--is immediately returned. If the set is a leaf containing a single primitive the range for that is calculated and returned. If the set is a union or an intersection, the function calls itself recursively for the two child operands, then combines the results appropriately. Finally, it makes sure that any attributes are inherited properly by the two sets that are returned by means of the pointer arguments.

Future enhancements

As mentioned in the Foreword, svLis was written both as a research and as a commercial geometric modeller. A number of current research projects are using it, and the results of those projects will be incorporated into svLis in the future. Additional facilities, not linked to a particular project, are being developed as well. This section gives a list of some of the current plans; I should say that directions--particularly on the research side--may change, so some objectives may be reduced in priority and some new aims may be introduced.

Distances. SvLis will shortly have nearest-leaf-set-to-a-point queries, and possibly also maximum and minimum distances between sets queries.
Interference. SvLis will have code in to detect when a pair of sets overlap, touch, or are distinct.
Feature recognition. This will allow you to make a svLis model of a feature, and then search for instances of that feature in a larger model under translation, rotation, and scale-change. It will also allow parameterized features to be defined, and then for searches to be done for instances which will return the matching parameter values.
Minkowski or vector sums . These will allow offset surfaces and much more to be computed from svLis models.
Motion. This will allow mechanisms to be modelled.
Connected components. This will allow analysis of whether or not a set represents one, or two or more, separate lumps in space.
Mixed algebraic and set-operators. At the moment, primitives are made by arithmetic and transcendental functions, then set-theory is done on the resulting potential-function inequalities. This will remove the demarcation, and allow arithmetic to be done on sets, which permits the convenient definition of a number of shapes.
Unidirectional scaling. This will allow shapes to be stretched in one direction only.
Regularization. This will deal with the situation when, for example, you intersect two primitives with a common face--this should not leave a zero-thickness solid. If you want one of them you should be using the sheet facilities provided by the abs function anyway.
Conversion of solids to shells. Take away the inside of a solid, leaving a zero-thickness shell made of sheets.
Digital Voronoi diagrams. This is not the place to describe what Voronoi diagrams are , but they form the basis of many finite-element schemes, and are also useful in skeletonization. I intend to introduce code into svLis to compute digital Voronoi diagrams of geometric models.
Parametric curves and surfaces . SvLis will remain based mainly on implicit geometry, but I have a research student working on the incorporation of parametric surfaces in svLis.

A number of items have also been identified that are for applications writers to implement outside svLis. Here is a (necessarily incomplete) list:

Further divider decision procedures. SvLis will have a number which implement its own requirements. It is up to you to add to these if you want.
Constraints. It should be easy to use a constraint resolver with svLis.
Tolerances. Nothing will be provided beyond the information already offered by user-defined attributes.
Two-dimensional operations. No procedures will be provided to work within sheets.
Sweeps and envelopes. These are for applications writers, apart from the Minkowski sums already mentioned.
Fancy renderers. Facets are available, and there is a ray tracer. Nothing else will be provided.
Non-linear transforms . `Bends', and other operations that distort primitives.
Cellular models . Beyond the sheet and wire functions already supplied, svLis will support no structures within sets. More than one set can be in the same physical place, of course, but it's up to the dividers you write to sort out what's going on.
Explicit boundary representation. SvLis will not have functions for doing Euler operations on faces and edges and dealing with other surface topology.
Vector fields. You can program your own, but they will not form part of the svLis kernel.

Next:Afterword Up:SvLis Introduction Previous:Sets, models, and DIY

Adrian Bowyer