C[omp]ute

From: "andrew cooke" <andrew@...>

Date: Sat, 24 Feb 2007 09:37:25 -0300 (CLST)

Kragen Sitaker (and wife Beatrice) is here for a couple of nights.  Last
night he was showing me a program he'd written in Javascript to display
images of 3D models.

Most of the program was the usual geometry stuff, but two things surprised
me.  First, the representation of objects, which was three arrays: an
array of points (coordinate triplets, then an array of lines (pairs of
indices into the array of points), then an array of polygons (lists of
indices into the array of lines).  In practice the polygons were always
triangles.

Is this a standard representation?  I thought it was neat.  It extends
neatly to a further array of volumes, which would be lists of indices into
the polygons.  However, in some way it's too general - there's no
constraint that all the lines in a polygon are coplanar, or that they form
closed loops (you can try to evade this by joining first and last points,
but that doesn't work so well if these are more general 2D figures with
holes).  Similarly, in higher dimensions, there's no guarantee that a
volume is "sealed" by the surfaces.

An alternative would be a less general approach that used surfaces as the
fundamental component.  Each would be defined by a point and a normal
vector.  Lines would then be intersections of planes.  Volumes would still
need checks for completeness and/or 'superfluous' surfaces.

The second interesting idea was an "extrusion" function used to generate
models from simpler components.  The way I understood it first was as a
fairly simple mathematical operation which takes a component (point or
line) and adds a further dimension.  So the following returns a cube:

  extrude(K,
    extrude(J,
       extrude(I, O)))

where I, J, and K are the normal unit vectors and O is the origin.

However, as far as I can tell, the implementation is rather different.  It
seems to be implemented as an operation that transforms the points in a
component and then "reconnects" the new points in "the way you would
expect" given the description above.  So if there are two points P0 and
Q0, they are transformed to P1 and Q1.  Then p0 and P1 are joined by a
line (same for Q0 and Q1).  Next, if P0 and Q0 are connected then P1 and
Q1 are connected and a polygon constructed using P0, Q0, Q1, P1 (in fact,
two triangles).

Furthermore, this can be iterated, re-applying the transform to the new
set of points a specified number of times (and doing the connections).

This is very useful.  Not only does it give the cube construction earlier,
but it can be used to construct, for example a torus.  Start with a circle
and repeatedly extrude, rotating points about a point coplanar with the
initial circle, but lying outside.

But while it is useful it also seems to be ad-hoc.  Somehow although it
works like my original understanding of the function, it is rather
different.  It seems an odd primitive operation - maybe it is better
expressed as the function I originally described, plus rotation and
duplication.  One issue with doing that, though, is that you get
additional faces - the torus has internal faces where each "straight
tublet" joins the next.  Either that, or the cube is actually a
rectangular sleeve.

Andrew