DIRECTORY G3dBasic, G3dMatrix, G3dModel, G3dOctree, G3dPolygon, G3dShape, G3dVector, ImplicitAdapt, ImplicitDefs, ImplicitPoints, ImplicitPolygons, ImplicitSurface, IO, Random, Rope;

ImplicitSurfaceImpl: CEDAR PROGRAM
IMPORTS G3dMatrix, G3dModel, G3dOctree, G3dShape, G3dVector, ImplicitAdapt, ImplicitPoints, ImplicitPolygons, IO, Random, Rope 
EXPORTS ImplicitSurface

~ BEGIN

NoSurfacePoint:	PUBLIC ERROR = CODE;
abort:				ERROR = CODE;

Triple:			TYPE ~ G3dBasic.Triple;
Matrix:			TYPE ~ G3dMatrix.Matrix;
Viewport:			TYPE ~ G3dMatrix.Viewport;
Corner:			TYPE ~ G3dOctree.Corner;
Cube:				TYPE ~ G3dOctree.Cube;
CubeProc:		TYPE ~ G3dOctree.CubeProc;
CubeStack:		TYPE ~ G3dOctree.CubeStack;
Direction:			TYPE ~ G3dOctree.Direction;
Edge:				TYPE ~ G3dOctree.Edge;
Face:				TYPE ~ G3dOctree.Face;
Octant:			TYPE ~ G3dOctree.Octant;
Octree:			TYPE ~ G3dOctree.Octree;
OctreeMode:		TYPE ~ G3dOctree.OctreeMode;
OctreeRep:		TYPE ~ G3dOctree.OctreeRep;
TwoCorners:		TYPE ~ G3dOctree.TwoCorners;
TwoFaces:		TYPE ~ G3dOctree.TwoFaces;
PolygonProc:		TYPE ~ G3dPolygon.PolygonProc;
Shape:				TYPE ~ G3dShape.Shape;
Vertex:			TYPE ~ G3dShape.Vertex;
ColorProc:			TYPE ~ ImplicitDefs.ColorProc;
EdgeMode:		TYPE ~ ImplicitDefs.EdgeMode;
NormalProc:		TYPE ~ ImplicitDefs.NormalProc;
PolygonOkProc:	TYPE ~ ImplicitDefs.PolygonOkProc;
StatusProc:		TYPE ~ ImplicitDefs.StatusProc;
SurfaceProc:		TYPE ~ ImplicitDefs.SurfaceProc;
Surface:			TYPE ~ ImplicitDefs.Surface;
Target:			TYPE ~ ImplicitDefs.Target;
TextureProc:		TYPE ~ ImplicitDefs.TextureProc;
ValueProc:		TYPE ~ ImplicitDefs.ValueProc;
VertexOkProc:	TYPE ~ ImplicitDefs.VertexOkProc;
ROPE:				TYPE ~ Rope.ROPE;
MakeSurface: PUBLIC PROC [
surface: Surface,
octreeMode: OctreeMode,
valueProc: ValueProc,
threshold: REAL _ 1.0,
triangulate: BOOL ¬ FALSE,
vertexOkProc: VertexOkProc _ NIL,
polygonOkProc: PolygonOkProc _ NIL,
normalProc: NormalProc _ NIL,
colorProc: ColorProc _ NIL,
textureProc: TextureProc _ NIL,
statusProc: StatusProc _ NIL,
tolerance: REAL _ 0.0001,
edgeMode: EdgeMode _ binarySectioning,
clientData: REF ANY _ NIL]
~ {
IF statusProc = NIL OR statusProc[$MakeOctree] # $Abort THEN {
surface.octree _ MakeOctree[octreeMode, valueProc, threshold, normalProc, statusProc, clientData];
[] ¬ MakePolygons[surface, valueProc, threshold, triangulate, vertexOkProc, polygonOkProc, normalProc, colorProc, textureProc, statusProc, tolerance, edgeMode, clientData];
};
};

MakePolygons: PUBLIC PROC [
surface: Surface,
valueProc: ValueProc,
threshold: REAL _ 1.0,
triangulate: BOOL ¬ FALSE,
vertexOkProc: VertexOkProc _ NIL,
polygonOkProc: PolygonOkProc _ NIL,
normalProc: NormalProc _ NIL,
colorProc: ColorProc _ NIL,
textureProc: TextureProc _ NIL,
statusProc: StatusProc _ NIL,
tolerance: REAL _ 0.0001,
edgeMode: EdgeMode _ binarySectioning,
clientData: REF ANY _ NIL]
RETURNS [nEvaluations: INT ¬ 0]
~ {
ENABLE abort => CONTINUE;
CheckStatus: PROC [type: ATOM, commatize: BOOL _ FALSE] ~ {
IF statusProc = NIL THEN RETURN;
IF statusProc[type] = $Abort THEN ERROR abort;
IF NOT Rope.IsEmpty[msg] AND commatize THEN msg _ Rope.Concat[", ", msg];
IF NOT Rope.IsEmpty[msg] AND statusProc[msg] = $Abort THEN ERROR abort;
};
cubeProc: CubeProc ~ {
IF statusProc # NIL AND statusProc[cube] = $Abort THEN RETURN[FALSE];
};
msg: ROPE;
IF surface = NIL OR surface.octree = NIL THEN RETURN;
CheckStatus[$SetCorners, TRUE];
nEvaluations ¬ 
ImplicitPoints.SetTerminalCubeCornerValuesAndCrossedPoints[
surface.octree.root, valueProc, threshold, normalProc,
cubeProc, tolerance, edgeMode, clientData];
CheckStatus[$MakeVertices];
msg _ ImplicitPoints.SetSurfaceVertices[surface, surface.octree.root, valueProc, threshold, normalProc, cubeProc, vertexOkProc, clientData];
CheckStatus[$MakePolygons];
msg _ ImplicitPolygons.SetSurfacePolygons[
surface, surface.octree.root, triangulate, valueProc, threshold, cubeProc, polygonOkProc, clientData];
CheckStatus[$MakeNormals, TRUE];
ImplicitPolygons.SetFaceNormalsCenters[surface];
msg _ "normals";
CheckStatus[$MakeTextures, TRUE];
ImplicitPoints.SetVertexTextures[surface, textureProc, cubeProc, clientData];
ImplicitPoints.SetVertexColors[surface, colorProc, cubeProc, clientData];
msg _ IF textureProc # NIL THEN "texture" ELSE NIL;
CheckStatus[$Done];
};
MakeOctree: PUBLIC PROC [
octreeMode: OctreeMode,
valueProc: ValueProc,
threshold: REAL _ 1.0,
normalProc: NormalProc _ NIL,
statusProc: StatusProc _ NIL,
clientData: REF ANY _ NIL]
RETURNS [octree: Octree]
~ {
ENABLE abort => {IF octree # NIL THEN octree.completed _ FALSE; CONTINUE};
CheckStatus: PROC [ref: REF] ~ {
IF statusProc # NIL AND statusProc[ref] = $Abort THEN ERROR abort;
};
CheckStatus[$MakeOctree];
WITH t: octreeMode SELECT FROM
converge => octree _ ConvergeOctree[
t.rootSize, t.recurseMin, t.recurseMax, valueProc, threshold,, statusProc, clientData];
track => octree _ IF t.duringAdaptMax > 0
THEN ImplicitAdapt.Track[t.cubeSize, t.surfacePoint, valueProc, threshold, normalProc, statusProc, clientData, t.duringAdaptMax, t.flatness, t.tolerance]
ELSE TrackOctree[t.cubeSize, t.surfacePoint, valueProc, threshold, statusProc, clientData];
ENDCASE => RETURN;
TRUSTED {octree.mode _ octreeMode};
CheckStatus[IO.PutFR1["%g cubes", IO.int[G3dOctree.NTerminalCubes[octree.root]]]];
IF octreeMode.postAdaptMax > 0 THEN CheckStatus[$AdaptOctree];
IF octreeMode.postAdaptMax > 0 THEN {
rope: ROPE _ ImplicitAdapt.Subdivide[octree.root, octreeMode.postAdaptMax, octreeMode.flatness, valueProc, threshold, normalProc, statusProc, clientData];
CheckStatus[rope];
};
G3dOctree.SetOctreeFields[octree];
};

TrackOctree: PUBLIC PROC [
cubeSize: REAL,
surfacePoint: Triple,
valueProc: ValueProc,
threshold: REAL _ 1.0,
statusProc: StatusProc _ NIL,
clientData: REF ANY _ NIL]
RETURNS [o: Octree]
~ {
ENABLE abort => {IF o # NIL THEN o.completed _ FALSE; CONTINUE};
ActiveFaces: TYPE ~ ARRAY Face OF BOOL _ ALL[FALSE];
Reject: CubeProc ~ {IF cube.refAny = $Rejected THEN cube.parent.kids[cube.octant] _ NIL};
CheckStatus: PROC [cube: Cube] ~ {
IF statusProc # NIL THEN SELECT statusProc[cube] FROM
$Abort		=> ERROR abort;
$RejectCube	=> {cube.refAny _ $Rejected; o.nCubes _ o.nCubes-1; rejected _ TRUE};
ENDCASE;
};
GetActiveFaces: PROC [cube: Cube] RETURNS [activeFaces: ActiveFaces] ~ {
ImplicitPoints.SetCornerValues[cube, valueProc, threshold, clientData];
FOR e: Edge IN Edge DO
corners: TwoCorners _ G3dOctree.EdgeCorners[cube, e];
IF corners.c0.inside # corners.c1.inside AND
NOT corners.c0.outOfRange AND
NOT corners.c1.outOfRange THEN {
twoFaces: TwoFaces ~ G3dOctree.EdgeFaces[e];
activeFaces[twoFaces.f0] _ activeFaces[twoFaces.f1] _ TRUE;
};
ENDLOOP;
};
ProcessTopOfStack: PROC [cubeStack: CubeStack] ~ {
new: Cube;
cube: Cube _ G3dOctree.ReadTopOfCubeStack[cubeStack];
IF cube.refAny # $Rejected THEN {
activeFaces: ActiveFaces ~ GetActiveFaces[cube];
FOR ff: Face IN Face DO
IF activeFaces[ff] AND G3dOctree.FaceNeighbor[cube, ff] = NIL THEN {
o.root _ G3dOctree.AddCube[cube, ff, FALSE];
o.nCubes _ o.nCubes+1;
IF NOT (new _ G3dOctree.FaceNeighbor[cube, ff]).terminal THEN ERROR;
G3dOctree.WriteBottomOfCubeStack[new, cubeStack];
CheckStatus[new];
};
ENDLOOP;
};
};
rejected: BOOL _ FALSE;
cubeStack: CubeStack _ G3dOctree.NewCubeStack[20000];
o _ NEW[OctreeRep _ [mode: [0, 0.0, 0.001, track[cubeSize, surfacePoint, 0]]]];
o.root _ G3dOctree.NewCube[cubeSize, surfacePoint];
G3dOctree.WriteBottomOfCubeStack[o.root, cubeStack];
CheckStatus[o.root];
WHILE NOT G3dOctree.CubeStackEmpty[cubeStack] DO
ProcessTopOfStack[cubeStack];
ENDLOOP;
IF rejected AND o.nCubes > 1 THEN G3dOctree.ApplyToTerminal[o.root, Reject];
o.completed _ TRUE;
};

ConvergeOctree: PUBLIC PROC [
rootSize: REAL,
recurseMin: NAT,
recurseMax: NAT,
valueProc: ValueProc,
threshold: REAL _ 1.0,
surfaceProc: SurfaceProc _ NIL,
statusProc: StatusProc _ NIL,
clientData: REF ANY _ NIL]
RETURNS [o: Octree]
~ {
ENABLE abort => {o.completed _ FALSE; CONTINUE};
localSurfaceProc: SurfaceProc ~ IF surfaceProc # NIL THEN surfaceProc ELSE DefaultSurface;
DefaultSurface: SurfaceProc ~ {
inside, once: BOOL _ FALSE;
IF cube = NIL THEN RETURN[FALSE];
FOR o: Octant IN Octant DO
c: Corner ~ cube.corners[o];
IF NOT c.valueSet
THEN ImplicitPoints.SetCornerValue[c, valueProc[c.point, clientData, c]-threshold];
IF c.nearestSet AND G3dOctree.PointInCube[c.nearest, cube] THEN RETURN[TRUE];
IF c.outOfRange THEN LOOP;
IF NOT once
THEN {inside _ c.inside; once _ TRUE}
ELSE IF c.inside # inside THEN RETURN[TRUE];		-- surface crosses cube
ENDLOOP;
RETURN[FALSE];
};
Inner: PROC [cube: Cube] ~ {
IF cube.level < recurseMax THEN {
G3dOctree.Subdivide[cube];
FOR o: Octant IN Octant DO
kid: Cube ~ cube.kids[o];
IF kid.level = 1 AND statusProc # NIL AND statusProc[kid]=$Abort THEN ERROR abort;
IF cube.level <= recurseMin OR localSurfaceProc[kid] 
THEN Inner[kid]
ELSE cube.kids[o] _ NIL;
ENDLOOP;
}
ELSE cube.terminal _ TRUE;
};
o _ NEW[OctreeRep _ [mode: [0, 0.0, 0.001, converge[rootSize, recurseMin, recurseMax]]]];
Inner[o.root _ G3dOctree.NewCube[rootSize]];
o.completed _ TRUE;
};
PointOnSurface: PUBLIC PROC [
surfaceHull: Cube,
valueProc: ValueProc,
threshold: REAL _ 1.0,
recurseLimit: NAT,
clientData: REF ANY _ NIL]
RETURNS [point: Triple]
~ {
ContainsSurface: PROC [cube: Cube] RETURNS [BOOL] ~ {
IF ImplicitPoints.IsCrossed[cube] THEN RETURN[TRUE];
FOR o: Octant IN Octant DO
c: Corner ~ cube.corners[o];
IF c.nearestSet AND G3dOctree.PointInCube[c.nearest, cube] THEN {
point _ c.nearest;
RETURN[TRUE];
};
ENDLOOP;
RETURN[FALSE];
};
ConvergeOnCrossedEdge: PROC [cube: Cube] RETURNS [point: Triple] ~ {
twoCorners: TwoCorners _ ImplicitPoints.CrossedEdgeCorners[cube];
in: Corner _ twoCorners.c0;
out: Corner _ twoCorners.c1;
IF in.value < 0.0 THEN {c: Corner _ in; in _ out; out _ c};
point _ SegmentConverge[in.point, out.point, in.value, out.value, valueProc, threshold, clientData, none, 0.00001,, 50].point;
};
Find: PROC [cube: Cube] RETURNS [found: BOOL _ FALSE] ~ {
DivideAndTestKids: CubeProc ~ {
G3dOctree.Subdivide[cube];
FOR o: Octant IN Octant DO
kid: Cube ~ cube.kids[o];
ImplicitPoints.SetCornerValues[kid, valueProc, threshold, clientData];
IF NOT ImplicitPoints.IsCrossed[kid] THEN LOOP;
point _ ConvergeOnCrossedEdge[kid];
found _ TRUE;
RETURN[FALSE];
ENDLOOP;
};
FOR level: NAT IN [0..recurseLimit) DO
G3dOctree.ApplyToLevel[cube, DivideAndTestKids, level];
IF found THEN RETURN;
ENDLOOP;
};
IF surfaceHull = NIL OR NOT Find[surfaceHull] THEN ERROR NoSurfacePoint ;
};

SurfacePoint: PUBLIC PROC [
in, out: Triple,
valueProc: ValueProc,
threshold: REAL _ 1.0,
clientData: REF ANY _ NIL]
RETURNS [p: Triple]
~ {
vIn: REAL _ valueProc[in, clientData]-threshold;
vOut: REAL _ valueProc[out, clientData]-threshold;
p _ IF vIn*vOut > 0.0
THEN FindStart[G3dVector.Midpoint[in, out], valueProc, 0.001, threshold]
ELSE SegmentConverge[in, out, vIn, vOut, valueProc, threshold, clientData].point;
};

FindStart: PUBLIC PROC [
ballpark: Triple,
valueProc: ValueProc,
size, level: REAL,
clientData: REF ANY ¬ NIL]
RETURNS [c: Triple]
~ {
Found: TYPE ~ RECORD [bad: BOOL, p: Triple];
Find: PROC [sign: {negative, positive}] RETURNS [found: Found ¬ [FALSE, ballpark]] ~ {
value: REAL;
FOR i: NAT IN [0..5000) DO
found.p.x ¬ found.p.x+size*(Random.NextInt[rs]/REAL[LAST[INT]]-0.5);
found.p.y ¬ found.p.y+size*(Random.NextInt[rs]/REAL[LAST[INT]]-0.5);
found.p.z ¬ found.p.z+size*(Random.NextInt[rs]/REAL[LAST[INT]]-0.5);
value ¬ valueProc[found.p, clientData]-level;
IF (sign = positive AND value > 0) OR (sign = negative AND value < 0) THEN RETURN;
size ¬ size*1.005;
ENDLOOP;
found.bad ¬ TRUE;
};
rs: Random.RandomStream ¬ Random.Create[];
pos: Found ¬ Find[positive];
neg: Found ¬ Find[negative];
IF pos.bad OR neg.bad
THEN ERROR NoSurfacePoint
ELSE c ¬ SegmentConverge[pos.p, neg.p, valueProc[pos.p, clientData], valueProc[neg.p, clientData], valueProc, level, clientData].point;
};

SegmentConverge: PUBLIC PROC [
pIn, pOut: Triple,
vIn, vOut: REAL,
valueProc: ValueProc,
threshold: REAL _ 1.0,
clientData: REF ANY _ NIL,
direction: Direction _ none,
tolerance: REAL _ 0.0001,
edgeMode: EdgeMode _ binarySectioning,
nTriesLimit: NAT _ 15]
RETURNS [t: Target ¬ [[], 0.0, 8]]
~ {
IF vIn < 0.0 THEN {temp: Triple ¬ pIn; pIn ¬ pOut; pOut ¬ temp};
THROUGH [0..8) DO
p: Triple _ SELECT direction FROM
n, f => [pIn.x, pIn.y, 0.5*(pIn.z+pOut.z)],
b, t => [pIn.x, 0.5*(pIn.y+pOut.y), pIn.z],
l, r => [0.5*(pIn.x+pOut.x), pIn.y, pIn.z],
ENDCASE => G3dVector.Midpoint[pIn, pOut];
IF (t.value ¬ valueProc[p, clientData]-threshold) > 0.0 THEN pIn ¬ p ELSE pOut ¬ p;
ENDLOOP;
t.point ¬ G3dVector.Midpoint[pIn, pOut];
};

Diverge: PROC [root: Cube] ~ {
cubeProc: CubeProc ~ {
FOR e: Edge IN Edge DO
corners: TwoCorners _ G3dOctree.EdgeCorners[cube, e];
IF corners.c0.inside # corners.c1.inside THEN {
c0, c1: Cube;
faces: TwoFaces ~ G3dOctree.EdgeFaces[e];
IF (c0 _ G3dOctree.FaceNeighbor[cube, faces.f0]) = NIL
THEN c0 _ G3dOctree.AddCube[cube, faces.f0, --FALSE?--];
IF (c1 _ G3dOctree.FaceNeighbor[cube, faces.f1]) = NIL
THEN c1 _ G3dOctree.AddCube[cube, faces.f1, --FALSE?--];
IF G3dOctree.FaceNeighbor[c0, faces.f1] = NIL
THEN [] _ G3dOctree.AddCube[c0, faces.f1, --FALSE?--];
};
ENDLOOP;
};
G3dOctree.ApplyToTerminal[root, cubeProc];
};
ShapeFromSurface: PUBLIC PROC [surface: Surface] RETURNS [shape: Shape] ~ {
IF surface # NIL AND surface.vertices # NIL AND surface.polygons # NIL THEN {
shape _ NEW[G3dShape.ShapeRep];
shape.matrix _ G3dMatrix.Identity[];
shape.type _ $ConvexPolygon;
shape.surfaces _ ImplicitPolygons.DecodePolygons[surface];
shape.vertices _ NEW[G3dShape.VertexSequenceRep[surface.vertices.length]];
shape.vertices.length _ surface.vertices.length;
shape.vertices.valid[normal] _ surface.vertexValidities[normal];
shape.vertices.valid[color] _ surface.vertexValidities[color];
shape.vertices.valid[texture] _ surface.vertexValidities[texture];
FOR n: NAT IN [0..surface.vertices.length) DO
v: Vertex _ shape.vertices[n] _ NEW[G3dShape.VertexRep];
surfaceVertex: Vertex _ surface.vertices[n];
v.point _ surfaceVertex.point;
IF surface.vertexValidities[normal] THEN v.normal _ surfaceVertex.normal;
IF surface.vertexValidities[texture] THEN v.texture _ surfaceVertex.texture;
IF surface.vertexValidities[color] THEN v.color _ surfaceVertex.color;
ENDLOOP;
shape.faces _ NEW[G3dShape.FaceSequenceRep[shape.surfaces.length]];
shape.faces.length _ shape.surfaces.length;
FOR n: NAT IN [0..shape.surfaces.length) DO
f: G3dShape.Face _ shape.faces[n] _ NEW[G3dShape.FaceRep];
f.normal _ surface.faceNormals[n];
f.center _ surface.faceCenters[n];
ENDLOOP;
shape.edges _ G3dShape.MakeEdges[shape];
G3dModel.SetCurves[shape];
};
};

SetSurfaceCurves: PUBLIC PROC [surface: Surface] ~ {
shape: Shape _ ShapeFromSurface[surface];
shape.edges _ G3dShape.MakeEdges[shape];
surface.curves _ G3dModel.MakeCurves[
ImplicitPoints.DecodePoints[surface],
ImplicitPoints.DecodeNormals[surface],
shape.edges];
surface.curvesValid _ TRUE;
};
NPolygons: PUBLIC PROC [surface: Surface] RETURNS [CARDINAL] ~ {
RETURN[IF surface = NIL THEN 0 ELSE surface.nPolygons];
};

NTriangles: PROC [surface: Surface] RETURNS [nTriangles: CARDINAL _ 0] ~ {
EachPoly: PolygonProc ~ {nTriangles _ nTriangles+polygon.length-2};
ImplicitPolygons.ApplyToSurfacePolygons[surface, EachPoly];
};

NEdges: PUBLIC PROC [surface: Surface] RETURNS [nEdges: CARDINAL _ 0] ~ {
CountEdges: PolygonProc ~ {nEdges _ polygon.length};
ImplicitPolygons.ApplyToSurfacePolygons[surface, CountEdges];
};

NVertices: PUBLIC PROC [surface: Surface] RETURNS [CARDINAL] ~ {
RETURN[IF surface = NIL OR surface.vertices = NIL THEN 0 ELSE surface.vertices.length];
};

EulerNumber: PUBLIC PROC [surface: Surface] RETURNS [CARDINAL] ~ {
RETURN[NPolygons[surface]-NEdges[surface]+NVertices[surface]];
};
SurfaceOK: PUBLIC PROC [surface: Surface] RETURNS [ok: BOOL] ~ {
ok _ surface # NIL AND surface.vertices # NIL AND surface.polygons # NIL;
};

VerticesOK: PUBLIC PROC [surface: Surface, view: Matrix, viewport: Viewport]
RETURNS [ok: BOOL]
~ {
IF (ok _ SurfaceOK[surface])
THEN ImplicitPoints.SetVertexScreenCoords[surface, view, viewport];
};

VertexNormalsOK: PUBLIC PROC [surface: Surface] RETURNS [ok: BOOL] ~ {
ok _ SurfaceOK[surface];
IF ok AND NOT surface.vertexValidities[normal] THEN ImplicitPoints.SetVertexNormals[surface];
};

FaceNormalsCentersOK: PUBLIC PROC [surface: Surface] RETURNS [ok: BOOL] ~ {
ok _ SurfaceOK[surface];
IF ok AND (surface.faceNormals = NIL OR surface.faceNormals.length = 0)
       OR (surface.faceCenters = NIL OR surface.faceCenters.length = 0)
THEN ImplicitPolygons.SetFaceNormalsCenters[surface];
};

SetNearest: PUBLIC PROC [corner: Corner, nearest: Triple, squareDistance: REAL _ 0.0] ~ {
IF corner = NIL THEN RETURN;
corner.nearest _ nearest;
corner.nearestSet _ TRUE;
corner.squareDistance _ squareDistance;
};

CornerWithMaxValue: PUBLIC PROC [cube: Cube] RETURNS [corner: Corner] ~ {
max: REAL _ -100000.0;
FOR o: Octant IN Octant DO
c: Corner ~ cube.corners[o];
IF c.value > max THEN {corner _ c; max _ c.value};
ENDLOOP;
};

END.


φ
ImplicitSurfaceImpl.mesa
Copyright c 1985 by Xerox Corporation.  All rights reserved.
Bloomenthal, February 27, 1993 3:37 pm PST
Surface Creation
Octree Creation
Diverge[root]; -- suspect
Surface Computation
SegmentConverge: PUBLIC PROC [
pIn, pOut: Triple,
vIn, vOut: REAL,
valueProc: ValueProc,
threshold: REAL _ 1.0,
clientData: REF ANY _ NIL,
direction: Direction _ none,
tolerance: REAL _ 0.0001,
edgeMode: EdgeMode _ binarySectioning,
nTriesLimit: NAT _ 15]
RETURNS [Target]
~ {
Inner: PROC [pIn, pOut: Triple, vIn, vOut: REAL] RETURNS [Target] ~ {
point: Triple;
a, d, dAbs, v: REAL _ 0.5;
IF edgeMode = regulaFalsi THEN {
dV: REAL ~ vIn-vOut;
IF dV # 0.0 THEN a _ vIn/dV;
};
d _ SELECT direction FROM
n, f => pOut.z-pIn.z,
b, t => pOut.y-pIn.y,
l, r => pOut.x-pIn.x,
ENDCASE =>	G3dVector.Distance[pIn, pOut];
dAbs _ ABS[d];
point _ SELECT direction FROM
n, f => [pIn.x, pIn.y, pIn.z+a*d],
b, t => [pIn.x, pIn.y+a*d, pIn.z],
l, r => [pIn.x+a*d, pIn.y, pIn.z],
ENDCASE => IF edgeMode = regulaFalsi
THEN G3dVector.Interp[a, pIn, pOut]
ELSE G3dVector.Midpoint[pIn, pOut];
v _ valueProc[point, clientData]-threshold;
IF nTries = 0 THEN epsilon _ dAbs*tolerance;
nTries _ nTries+1;
nTriesLimit shouldn't be necessary for well-behaved, exactly evaluated functions, but . . .
IF dAbs < epsilon THEN RETURN[[point, v, nTries]];
IF edgeMode = regulaFalsi AND nTries > nRegulaFalsiTriesLimit THEN {
nTries _ nTriesLimit/3;
edgeMode _ binarySectioning;
};
IF nTries > nTriesLimit THEN RETURN[[point, v, nTries]];
RETURN[IF v < 0.0
THEN Inner[pIn, point, vIn, v]
ELSE Inner[point, pOut, v, vOut]];
};
epsilon: REAL;
nTries: NAT _ 0;
nRegulaFalsiTriesLimit: NAT _ nTriesLimit/2;
IF direction = none THEN direction _ G3dOctree.DirectionFromPoints[pIn, pOut];
IF valueProc = NIL
THEN RETURN[[G3dVector.Midpoint[pIn, pOut], 0]]
ELSE RETURN[Inner[pIn, pOut, vIn, vOut]];
};

Add cubes to root which were originally missed but face cubes cut by the surface.
Conversions
Attributes
Note: We should make this a PUBLIC proc sometime.
Miscellany
ΚΈ•NewlineDelimiter

™™Jšœ
Οm
œ1™<J™*J˜JšΟk	œ­
˜Ά
J˜—šΠblœžœ
ž˜"Jšžœx˜Jšžœ˜J˜—šœž˜J˜Jšœžœ
žœžœ
˜$šœž	œžœ
˜J˜—Jšœ
žœ˜!Jšœ
žœ˜"Jšœžœ˜&Jšœ
žœ˜"Jšœžœ˜Jšœžœ˜%Jšœžœ˜'Jšœ
žœ˜(Jšœžœ˜Jšœžœ˜Jšœ
žœ˜"Jšœ
žœ˜"Jšœžœ˜)Jšœ
žœ˜'Jšœžœ˜)Jšœ	žœ˜%Jšœžœ˜,Jšœžœ˜ Jšœžœ˜!Jšœ
žœ˜+Jšœ	žœ˜(Jšœžœ˜,Jšœžœ˜1Jšœžœ˜,Jšœžœ˜.Jšœžœ˜'Jšœžœ˜%Jšœžœ˜.Jšœ
žœ˜*Jšœ
žœ˜/Jšžœžœžœ
˜—
headš
Οl™šΟnœžœ˜J˜J˜J˜Jšœžœ˜Jšœ
žœžœ
˜Jšœžœ
˜!Jšœžœ
˜#Jšœžœ
˜Jšœžœ
˜Jšœžœ
˜Jšœžœ
˜Jšœžœ
˜J˜&Jšœžœ
žœžœ
˜J˜šžœžœ
žœ"žœ˜>J˜bJ˜¬
J˜—J˜J˜—š‘œžœ˜J˜J˜Jšœžœ˜Jšœ
žœžœ
˜Jšœžœ
˜!Jšœžœ
˜#Jšœžœ
˜Jšœžœ
˜Jšœžœ
˜Jšœžœ
˜Jšœžœ
˜J˜&Jšœžœ
žœžœ
˜Jšžœžœ˜J˜Jšžœ
žœ
˜š
‘œžœžœ
žœžœ˜;Jšžœžœ
žœ
žœ
˜ Jšžœžœ
žœ˜.Jšžœ
žœžœžœ˜IJš
žœ
žœžœžœ
žœ˜GJ˜—šΟbœ˜Jšžœžœ
žœžœ
žœ
žœ˜EJ˜—Jšœžœ
˜
Jšžœžœ
žœžœ
žœ
žœ
˜5Jšœžœ˜˜˜;J˜6J˜+——J˜J˜Œ
J˜˜*J˜f—Jšœžœ˜ J˜0J˜Jšœžœ˜!J˜MJ˜IJšœžœžœ
žœžœ
žœ
˜3J˜J˜——š
 ™š‘
œžœ
žœ˜J˜J˜Jšœžœ˜Jšœžœ
˜Jšœžœ
˜Jšœžœ
žœžœ
˜Jšžœ˜J˜Jšžœžœ
žœ
žœžœžœ˜Jš‘œžœžœ˜ Jš
žœžœ
žœžœ
žœ˜BJ˜—J˜šžœžœ
ž˜˜$J˜W—šœžœ˜)Jšžœ•
˜™
JšžœW˜[—Jšžœžœ
˜—Jšžœ˜#Jšœžœžœ.˜RJšžœžœ˜>šžœžœ˜%Jšœžœ
˜š
J˜J˜—J˜"J˜J˜—š‘œ
žœ˜Jšœ
žœ
˜J˜J˜Jšœžœ˜Jšœžœ
˜Jšœžœ
žœžœ
˜Jšžœ˜J˜Jšžœžœžœ
žœžœžœ˜@Jš
œ
žœžœžœ
žœžœ
žœ˜4Jš‘œžœžœ!žœ˜Yš‘œžœ˜"š	žœžœ
žœ
žœž˜5Jšœžœ˜JšœKžœ˜QJšžœ
˜—J˜—š‘œžœžœ˜HJ˜Gšžœ	žœž˜J˜5šžœ'ž˜,Jšžœž˜šžœžœ˜ J˜,Jšœ6žœ
˜;J˜——Jšžœ
˜—J˜—š‘œžœ˜2J˜
J˜5šžœžœ˜!J˜0šžœ
žœž˜šžœžœ$žœ
žœ˜DJšœ%žœ˜,J˜Jšžœ
žœ3žœ
žœ
˜DJ˜1J˜J˜—Jšžœ
˜—J˜—J˜—Jšœ	žœžœ
˜J˜5JšœžœH˜OJ˜3J˜4J˜šžœ
žœ%ž˜0J˜Jšžœ
˜—Jšžœ
žœžœ+˜LJšœžœ
˜J˜J˜—š‘œ
žœ˜Jšœ
žœ
˜Jšœžœ
˜Jšœžœ
˜J˜Jšœžœ˜Jšœžœ
˜Jšœžœ
˜Jšœžœ
žœžœ
˜Jšžœ˜J˜Jšžœžœžœ˜0Jš	œ žœžœ
žœ
žœ˜Zš‘œ˜Jšœžœžœ
˜Jš
žœžœ
žœ
žœ
žœ˜!šžœžœž˜J˜šžœ
žœ˜JšžœC’
œ˜S—Jš
žœžœ'žœ
žœ
žœ˜MJšžœžœ
žœ
˜šžœ
žœ˜Jšžœžœ
˜%Jšžœ
žœžœ
žœ
žœΟc˜E—Jšžœ
˜—Jšžœ
žœ˜J˜—š‘œžœ˜šžœžœ˜!J˜šžœžœž˜J˜Jšžœžœžœ
žœžœ
žœ˜Ršžœžœ˜5Jšžœ˜Jšžœžœ
˜—Jšžœ
˜—J˜
—Jšžœžœ
˜J˜—JšœžœR˜YJ˜,Jšœžœ
˜Jšœ£
™J˜——š
 ™š‘œžœ˜J˜J˜Jšœžœ˜Jšœžœ
˜Jšœžœ
žœžœ
˜Jšžœ˜J˜š‘œžœžœžœ˜5Jšžœ žœ
žœ
žœ˜4šžœžœž˜J˜šžœžœ(žœ˜AJ˜Jšžœ
žœ˜
J˜—Jšžœ
˜—Jšžœ
žœ˜J˜—š‘œžœžœ˜DJ˜AJ˜J˜Jšžœžœ%˜;J˜~J˜—š
‘œžœžœ	žœžœ˜9š’œ˜J˜šžœžœž˜J˜J˜FJšžœ
žœžœ
žœ
˜/J˜#Jšœžœ
˜
Jšžœ
žœ˜Jšžœ
˜—J˜—šžœžœ
žœž˜&J˜7Jšžœžœ
žœ
˜Jšžœ
˜—J˜—Jšžœžœ
žœ
žœžœ
žœ˜IJ˜J˜—š‘œžœ
žœ˜Jš
œ˜Jš
œ˜Jšœžœ˜Jšœžœ
žœžœ
˜Jšžœ˜Jš
œ˜Jšœžœ’
œ
˜0Jšœžœ’
œ
˜2šœžœ˜JšžœD˜HJšžœM˜Q—J˜J˜—š‘	œžœ˜Jš
œ˜J˜Jšœ
žœ
˜Jšœžœ
žœžœ
˜Jšžœ˜Jš
œ˜Jšœžœžœžœ
˜,š
‘œžΟs
œ€
œ
€
œžœžœ˜VJšœžœ
˜šžœžœ
žœž˜Jšœ/žœ
žœ
žœ˜DJšœ/žœ
žœ
žœ˜DJšœ/žœ
žœ
žœ˜DJ˜-Jšžœžœžœžœžœ
žœ
˜RJ˜Jšžœ
˜—Jšœžœ
˜J˜—J˜*J˜J˜šžœ	žœ˜Jšžœ
žœ˜Jšžœƒ
˜‡
—J˜J˜—š‘œžœ
žœ˜J˜Jšœžœ
˜J˜Jšœžœ˜Jšœžœ
žœžœ
˜J˜Jšœžœ
˜J˜&Jšœ
žœ˜Jšžœ˜"Jš
œ˜Jšžœžœ/˜@šžœž˜šœžœž˜!J˜+J˜+J˜+Jšžœ"˜)—Jšžœ$’
œžœ	žœ
˜SJšžœ
˜—J˜(J˜J˜—š‘œžœ
žœ™J™Jšœžœ
™J™Jšœžœ™Jšœžœ
žœžœ
™J™Jšœžœ
™J™&Jšœ
žœ™Jšžœ	™Jš
œ™š‘œžœ žœžœ
™EJ™Jšœžœ™šžœžœ™ Jšœžœ™Jšžœ
žœ™J™—šœ
žœ
žœž™J™J™J™Jšžœ"™)—Jšœžœ
žœ™šœžœž™J™"J™"J™"šžœžœ™$Jšžœ™#Jšžœ™#——Jšœ
žœ’
œ
™+Jšžœžœ™,J™J™[J–16.0 24 .div 1 1 textColoršžœžœ
žœ™2šžœžœ!žœ™DJš
œ™J™J™—Jšžœžœ
žœ™8šžœ
žœ™Jšžœ
’œ™Jšžœ
’œ™"—J™—Jšœ	žœ
™Jšœžœ™Jšœžœ™,Jšžœžœ6™N•StartOfExpansion![v: 
Vector3d.Triple, s: 
REAL]šžœ
ž™Jšžœ
žœ$™/Jšžœ™)—J™J™—š‘œ
žœ˜J™Qš‘œ˜šžœ	žœž˜J˜5šžœ'žœ˜/J˜
J˜)šžœ1ž˜6Jšžœ(£
œ˜8—šžœ1ž˜6Jšžœ(£
œ˜8—šžœ(ž˜-Jšžœ&£
œ˜6—J˜—Jšžœ
˜—J˜—J˜*J˜——š
 ™š‘œžœ
žœžœ˜Kšžœžœ
žœžœ
žœžœ
žœ˜MJšœžœ˜J˜$J˜J˜:Jšœžœ6˜JJ˜0J˜@J˜>J˜Bšžœžœ
žœž˜-Jšœ žœ˜8J˜,J˜Jšžœ"žœ!˜IJšžœ#žœ#˜LJšžœ!žœ˜FJšžœ
˜—Jšœžœ2˜CJ˜+šžœžœ
žœž˜+Jšœ$žœ˜:Jš
œ"˜"Jš
œ"˜"Jšžœ
˜—J˜(Jš
œ˜J˜—J˜J˜—š‘œžœ˜4J˜)Jš
œ(˜(˜%J˜%J˜&Jš
œ
˜
—Jšœžœ
˜J˜——š
 
™
š
‘	œžœ
žœžœžœ˜@Jš
žœ
žœžœ
žœžœ˜7J˜J˜—š‘
œžœžœžœ	˜JJš
’1™1Jš’œ;˜CJ˜;J˜J˜—š
‘œžœ
žœžœ
žœ	˜IJš‘
œ*˜4J˜=J˜J˜—š
‘	œžœ
žœžœžœ˜@Jšžœ
žœžœ
žœžœ
žœžœ˜WJ˜J˜—š
‘œžœ
žœžœžœ˜BJšžœ8˜>J˜——š
 
™
š‘	œžœžœžœ˜@Jšœžœ
žœžœ
žœžœ
˜IJ˜J˜—š‘
œžœ5˜LJšžœžœ
˜Jš
œ˜šžœ˜Jšžœ?˜C—J˜J˜—š‘œžœžœžœ˜FJ˜Jšž€
œ€
ž€
žœ!€
ž€
œ)˜]J˜J˜—š‘œžœžœžœ˜KJ˜šžœžœžœ
žœ ˜GJšž	œžœ
žœ ˜GJšžœ1˜5—J˜J˜—š‘
œžœ
žœ3žœ˜YJšžœ
žœ
žœ
žœ
˜J˜Jšœžœ
˜J˜'J˜J˜—š‘œžœ
žœžœ˜IJšœžœ
˜šžœžœž˜J˜Jšžœžœ˜2Jšžœ
˜—J˜—J˜—šžœ
˜J˜—J˜—…—BP_ώ