QuadTree

IntroductionThis tutorial demonstrates how subclasses of the Node and QuadTree classes introduced in QuadTree: Python can be used to explore some aspects of blobby geometry. An example, of the interaction of positive and negative "blobby circles" is shown in figure 1. The quadtree (2D) technique shown in this tutorial is intended to be an introduction to 3D methods that use octrees.
Similar, but noninteracting, circles produced by cquadtree.py and visualized using RenderMan are shown in figure 2. For another tutorial that deals with blobby shapes refer to RSL: Blobby Effects
The Interaction of Positive & Negative Fields
Unlike figure 2 where the small green squares trace the circumferences of two circles,
those in figure 1 mark the boundary of two "clouds" of (scalar) values such that
their combined values are 0.5 or greater. The two dark red dots in figure 1 mark the
centers of two radial fields of values that have a maximum value of 1.0 (positive field)
and 1.0 (negative field) at the red dots and at a fixed radial distance have a value
0.0.
Another way of visualizing a scalar field is to represent its values as heights  figure 4.

Radial Distances and Field Values
The code presented later in this tutorial calculates the (scalar) field value at a point
in space according to its distance from one or more blobby geometries such as circles
and lines. The formula for converting a distance to a field value in the range 0 to 1
is taken from the research of Geoff Wyvill and Craig McPhetters "Data Structure for
Soft Objects", The Visual Computer, Vol 2 1986. Wyvill calls his geometries
Wyvill & McPhettersThis tutorial, in an attempt to be as pictorial as possible, will not delve into the mathematics of their "field function". Different researchers have different ways of using distances to calculate a scalar field. Their technique is used here because it does not rely on ray tracing. Their technique is relatively fast and generates smooth isocontours in 2D and smooth isosurfaces in 3D. The prefix "iso" simply means "equal", as in a contour or a surface sharing the same field value. The code that performs the calculation is shown next. 
Listing 1 (see blobby_quadtree.py)

Avoiding Sampling ErrorsA quadtree subdivides a rectangle only if it detects that any of its four (children) subrectangles spans an isocontour. Field values at each vertex might be calculated and if there is a mixture of values greater and smaller than 0.5 then the rectangle must be spanning an isocontour (figure 5).
Relying solely on vertex sampling will also fail if the isocontour is completely contained within the rectangle (figure 6) or if the isocontour only passes through an edge (figure 7). 


Figure 8 visualizes a quadtree that has relied solely on vertex sampling. Figure 9
demonstrates the use of a preliminary test that determines if the center of any of the
blobby circles are with a subrectangle. Figure 10 shows the effect of applying a third
test to determines if any of the edges of a subrectangle are within a certain distance
of the center of any blobby circle. The tests are applied in the following order, from
computationally cheapest to most expensive. 



Because adjacent subrectangles share vertices their field values are stored in a
dictionary that acts as a lookup table  see
The code in listing 2 should be saved in the same directory as
quadtree.py,
vectors.py and
distances.py.

Listing 2 (blobby_quadtree.py)

© 2002 Malcolm Kesson. All rights reserved.