ImplicitDrawImpl
Copyright Ó 1985, 1990 by Xerox Corporation. All rights reserved.
Bloomenthal, November 21, 1992 6:49 pm PST
DIRECTORY CedarProcess, Draw2d, G3dBasic, G3dCubeDraw, G3dDraw, G3dMatrix, G3dOctree, G3dPlane, G3dPolygon, G3dShape, G3dVector, Imager, ImagerPath, ImplicitDraw, ImplicitDefs, ImplicitPoints, ImplicitPolygons, ImplicitSurface, Real;
ImplicitDrawImpl: CEDAR PROGRAM
IMPORTS CedarProcess, G3dCubeDraw, G3dDraw, G3dOctree, G3dVector, Imager, ImagerPath, ImplicitPoints, ImplicitPolygons, ImplicitSurface, Real
EXPORTS ImplicitDraw
~ BEGIN
MarkType:  TYPE ~ Draw2d.MarkType;
NatSequence:  TYPE ~ G3dBasic.NatSequence;
Triple:   TYPE ~ G3dBasic.Triple;
Cube:    TYPE ~ G3dOctree.Cube;
Octant:   TYPE ~ G3dOctree.Octant;
Diagrammatic Progress
DiagramProgress: PUBLIC PROC [
context: Imager.Context,
surface: ImplicitDefs.Surface,
whatChanged: REF ANY,
refAny: REF ANY,
view: G3dMatrix.Matrix,
viewport: G3dMatrix.Viewport ¬ [],
currentCube: Cube ¬ NIL,
drawEdges: BOOL ¬ FALSE,
drawPolygons: BOOL ¬ FALSE,
drawRoots: BOOL ¬ FALSE]
~ {
Mark: PROC [mark: MarkType] ~ {
vertex: G3dShape.Vertex ¬ NARROW[refAny];
SELECT mark FROM
x => G3dDraw.Mark[context, vertex.point, view, vp,, x];
dot => G3dDraw.Box[context, vertex.point, view, vp, 3, 3];
ENDCASE;
};
root: Cube ¬ IF surface # NIL AND surface.octree # NIL THEN surface.octree.root ELSE NIL;
vp: G3dMatrix.Viewport ¬ viewport;
SELECT whatChanged FROM
$NewCube, $MakeOctree => {
IF drawEdges THEN G3dCubeDraw.SimpleCube[context, currentCube, view, vp,, dotted];
IF drawRoots THEN G3dCubeDraw.SimpleCube[context, root, view, vp, TRUE, solid];
};
$NewRoot =>
IF drawRoots THEN G3dCubeDraw.SimpleCube[context, root, view, vp, TRUE, solid];
$AdaptOctree => {
m: MarkType ¬ SELECT refAny FROM $Dot => dot, $Cross => cross, ENDCASE => x;
G3dDraw.Mark[context, G3dOctree.Center[currentCube], view, vp,, m];
};
$SetCorners => G3dCubeDraw.SimpleCube[context, currentCube, view, vp,, solid];
$MakePolygons =>
IF drawPolygons THEN DrawPolygon[context, surface, NARROW[refAny, NatSequence]];
$MakeVertices =>
IF drawPolygons THEN Mark[dot];
$MakeTextures =>
IF drawPolygons THEN Mark[x];
NIL => {
IF drawEdges THEN G3dCubeDraw.TerminalCubes[context, root, view, vp, dotted];
IF drawRoots THEN G3dCubeDraw.SimpleCube[context, root, view, vp, TRUE, solid];
};
ENDCASE;
};
DrawPolygon: PUBLIC PROC [
context: Imager.Context,
surface: ImplicitDefs.Surface,
polygon: NatSequence,
clipCube: Cube ¬ NIL,
directionSelect: G3dOctree.DirectionSelect ¬ xyz,
forInterpress: BOOL ¬ FALSE]
~ {
IF polygon = NIL OR polygon.length < 3 OR clipCube = NIL OR surface = NIL THEN RETURN;
FOR i: NAT IN [0..polygon.length) DO
IF NOT G3dOctree.PointInCube[surface.vertices[polygon[i]].point, clipCube, .05]
THEN RETURN;
ENDLOOP;
IF forInterpress
THEN {
t: Imager.Trajectory ¬ ImagerPath.MoveTo[surface.screens[polygon[0]].pos];
FOR n: NAT IN [1..polygon.length) DO
t ¬ ImagerPath.LineTo[t, surface.screens[polygon[n]].pos];
ENDLOOP;
Imager.SetStrokeJoint[context, round];
Imager.MaskStrokeTrajectory[context, t, TRUE];
}
ELSE {
Eq: PROC [r, s: REAL] RETURNS [b: BOOL] ~ INLINE {b ¬ ABS[r-s] < 0.0001};
Rnd: PROC [r: REAL] RETURNS [i: INT] ~ INLINE {i ¬ Real.Round[r]};
s0, s1: G3dBasic.Pair;
n0, n1: NAT ¬ polygon[polygon.length-1];
p0, p1: Triple ¬ surface.vertices[n0].point;
FOR i: NAT IN [0..polygon.length) DO
n0 ¬ n1;
p0 ¬ p1;
p1 ¬ surface.vertices[n1 ¬ polygon[i]].point;
IF directionSelect # xyz THEN SELECT directionSelect FROM
x => IF Eq[p0.x, p1.x] THEN LOOP;
y => IF Eq[p0.y, p1.y] THEN LOOP;
z => IF Eq[p0.z, p1.z] THEN LOOP;
xy => IF Eq[p0.x, p1.x] OR Eq[p0.y, p1.y] THEN LOOP;
xz => IF Eq[p0.x, p1.x] OR Eq[p0.z, p1.z] THEN LOOP;
yz => IF Eq[p0.y, p1.y] OR Eq[p0.z, p1.z] THEN LOOP;
ENDCASE;
s0 ¬ surface.screens[n0].pos;
s1 ¬ surface.screens[n1].pos;
G3dDraw.Line2d[context, [Rnd[s0.x], Rnd[s0.y]], [Rnd[s1.x], Rnd[s1.y]], solid];
ENDLOOP;
};
};
Drawing Surfaces with Hidden Lines Eliminated
DoWithPlanarContours: PUBLIC PROC [
octree: G3dOctree.Octree,
edgeMode: ImplicitDefs.EdgeMode,
valueProc: ImplicitDefs.ValueProc,
threshold: REAL ¬ 1.0,
connectProc: ImplicitDefs.ConnectProc,
clientData: REF ANY,
normal: Triple,     -- normal should be unit length
wMin, wMax, wDelta: REAL]
~ {
DoWithPlanarContour: PROC [plane: G3dPlane.Plane] ~ {
UnSet: G3dOctree.CubeProc ~ {
FOR o: Octant IN Octant DO cube.corners[o].valueSet ¬ FALSE; ENDLOOP;
};
Set: G3dOctree.CubeProc ~ {
FOR o: Octant IN Octant DO
c: G3dOctree.Corner ~ cube.corners[o];
IF NOT c.valueSet THEN ImplicitPoints.SetCornerValue[
c, c.point.x*plane.x+c.point.y*plane.y+c.point.z*plane.z+plane.w];
ENDLOOP;
};
Converge: PROC [p0, p1: Triple, v0, v1: REAL, nTriesLimit: NAT] RETURNS [t: Triple] ~ {
pIn, pOut: Triple;
vIn, vOut: REAL;
IF v0 > 0.0
THEN {pIn ¬ p0; pOut ¬ p1; vIn ¬ v0; vOut ¬ v1}
ELSE {pIn ¬ p1; pOut ¬ p0; vIn ¬ v1; vOut ¬ v0};
t ¬ ImplicitSurface.SegmentConverge[pIn, pOut, vIn, vOut, HLEValue, threshold, clientData,, octree.mode.tolerance,, nTriesLimit].point;
};
polygonProc: G3dPolygon.PolygonProc ~ {
Contour: PROC [p0, p1: Triple, depth, nTriesLimit: NAT] ~ {
IF depth = 3
THEN connectProc[p0, p1]
ELSE {
SetValues: PROC [mul: REAL] ~ {
xMul: Triple ¬ G3dVector.Mul[x, mul*len];
x0 ¬ G3dVector.Add[m, xMul];
x1 ¬ G3dVector.Sub[m, xMul];
v0 ¬ HLEValue[x0, clientData];
v1 ¬ HLEValue[x1, clientData];
};
m, x0, x1: Triple ¬ G3dVector.Midpoint[p0, p1];
dif: Triple ¬ G3dVector.Sub[p1, p0];
len, v0, v1: REAL ¬ G3dVector.Length[dif];
x: Triple ¬ G3dVector.Unit[G3dVector.Cross[normal, dif]];
SetValues[0.2];
IF (v0 > 0.0) = (v1 > 0.0) THEN SetValues[0.4];
IF (v0 > 0.0) # (v1 > 0.0) THEN {
p: Triple ¬ Converge[x0, x1, v0, v1, nTriesLimit];
Contour[p0, p, depth+1, nTriesLimit-1];
Contour[p, p1, depth+1, nTriesLimit-1];
};
};
};
p0, p1: Triple ¬ [];
i0: NAT ¬ polygon[polygon.length-1];
FOR n: NAT IN [0..polygon.length) DO
i: NAT ¬ polygon[n];
values[i] ¬ HLEValue[vertices[i], clientData];
ENDLOOP;
FOR n: NAT IN [0..polygon.length) DO
i1: NAT ¬ polygon[n];
IF (values[i0] > 0.0) # (values[i1] > 0.0) THEN {
p: Triple ¬ Converge[vertices[i0], vertices[i1], values[i0], values[i1], 6];
IF p0 = [] THEN p0 ¬ p ELSE IF p1 = [] THEN p1 ¬ p ELSE EXIT;
};
i0 ¬ i1;
ENDLOOP;
IF p0 # [] AND p1 # [] THEN Contour[p0, p1, 1, 15];
};
SetPlaneCrossings: PROC [cube: Cube] ~ {
id: NAT ¬ 0;
crossedEdges: G3dOctree.CrossedEdges ¬ ImplicitPoints.CubeCrossedEdges[cube];
FOR e: G3dOctree.Edge IN G3dOctree.Edge DO
x: G3dOctree.CrossedEdge ¬ crossedEdges[e];
IF x.cIn # NIL THEN {
NewCross: PROC RETURNS [cross: G3dOctree.Cross] ~ {
dif: REAL ¬ x.cIn.value-x.cOut.value;
point: Triple ¬ x.cIn.point;
IF dif # 0.0 THEN {
alpha: REAL ¬ x.cIn.value/dif;
SELECT d FROM
l, r => point.x ¬ (1.0-alpha)*x.cIn.point.x+alpha*x.cOut.point.x;
b, t => point.y ¬ (1.0-alpha)*x.cIn.point.y+alpha*x.cOut.point.y;
n, f => point.z ¬ (1.0-alpha)*x.cIn.point.z+alpha*x.cOut.point.z;
ENDCASE => ERROR;
};
vertices[id] ¬ point;
cross ¬ NEW[G3dOctree.CrossRep ¬ [id: id]];
id ¬ id+1;
};
d: G3dOctree.Direction ¬ G3dOctree.DirectionFromOctants[x.oIn, x.oOut];
c: G3dOctree.Corner ~ SELECT d FROM l, b, n => x.cIn, ENDCASE => x.cOut;
SELECT d FROM
l, r => c.lCross ¬ NewCross[];
b, t => c.bCross ¬ NewCross[];
n, f => c.nCross ¬ NewCross[];
ENDCASE => ERROR;
};
ENDLOOP;
};
OctreeDescend: PROC [cube: Cube] ~ {
CedarProcess.CheckAbort[];
IF cube = NIL OR NOT ImplicitPoints.IsCrossed[cube] THEN RETURN;
IF cube.terminal
THEN {
SetPlaneCrossings[cube];
[] ¬ ImplicitPolygons.PolygonizeCube[cube, polygonProc, polygon, FALSE];
}
ELSE FOR o: Octant IN Octant DO OctreeDescend[cube.kids[o]]; ENDLOOP;
};
HLEValue: ImplicitDefs.ValueProc ~ {        -- heart of the HLE
value ¬ valueProc[point, clientData];
FOR n: NAT IN [0..nPreviousSlices) DO
point ¬ G3dVector.Sub[point, normalDelta];
value ¬ MAX[value, valueProc[point, clientData]];
IF value >= threshold THEN EXIT;        -- hidden
ENDLOOP;
};
G3dOctree.Apply[octree.root, UnSet];
CedarProcess.CheckAbort[];
G3dOctree.Apply[octree.root, Set];
OctreeDescend[octree.root];
};
polygon: NatSequence ¬ NEW[G3dBasic.NatSequenceRep[24]];
vertices: G3dBasic.TripleSequence ¬ NEW[G3dBasic.TripleSequenceRep[24]];
values: G3dBasic.RealSequence ¬ NEW[G3dBasic.RealSequenceRep[24]];
normalDelta: Triple ¬ G3dVector.Mul[normal, wDelta];
nPreviousSlices: NAT ¬ 0;
IF octree # NIL THEN FOR w: REAL ¬ wMin, w+wDelta WHILE w <= wMax DO
DoWithPlanarContour[[normal.x, normal.y, normal.z, wMax+wMin-w]]; -- wMax to wMin
nPreviousSlices ¬ nPreviousSlices+1;
ENDLOOP;
};
END.
..
DrawSurface: PUBLIC PROC [
context: Context,
surface: Surface,
view: Matrix,
drawTriangles: BOOL ¬ FALSE,
drawPolygons: BOOL ¬ FALSE,
drawBackFaces: BOOL ¬ TRUE,
drawVertices: BOOL ¬ FALSE,
labelVertices: BOOL ¬ FALSE,
drawNormals: BOOL ¬ FALSE,
drawOctree: BOOL ¬ FALSE,
drawValues: BOOL ¬ FALSE,
drawCurves: BOOL ¬ FALSE,
clipCube: Cube ¬ NIL,
directionSelect: DirectionSelect ¬ xyz,
forInterpress: BOOL ¬ FALSE,
zip: Zip ¬ NIL]
~ {
color: BOOL ¬ NOT forInterpress AND FALSE; -- NOT Draw2d.IsLF[context];
IF surface = NIL THEN RETURN;
ImplicitPoints.SetVertexScreenCoords[surface, view];
IF drawOctree AND surface.octree # NIL THEN {
IF color
THEN {
DrawCube: CubeProc ~ {
IF cube.level > limit THEN RETURN;
Imager.SetStrokeWidth[context, REAL[MAX[0, depth-2*cube.level]]/REAL[depth]];
G3dCubeDraw.SimpleCube[context, cube, view, FALSE, solid, zip];
};
depth: NAT ¬ G3dOctree.DepthOf[surface.octree.root];
limit: NAT ¬ depth-2;
Imager.SetColor[context, ImagerColor.ColorFromRGB[[0.0, 0.0, 1.0]]];
G3dOctree.Apply[surface.octree.root, DrawCube];
}
ELSE {
IF forInterpress THEN Imager.SetGray[context, 0.6];
G3dCubeDraw.TerminalCubes[context, surface.octree.root, view, solid, zip];
};
};
Imager.SetGray[context, 1.0];
IF drawValues THEN {
cornerProc: CornerProc ~ {
pair: Pair ~ G3dMatrix.TransformD[corner.point, view];
Process.CheckForAbort[];
Draw2d.Label[context, pair, IO.PutFR["%4.3f", IO.real[corner.value]]];
IF corner.inside THEN Draw2d.Mark[context, pair, dot];
};
G3dOctree.ApplyToTerminalCorners[surface.octree.root, cornerProc];
};
IF color AND (drawTriangles OR drawPolygons) THEN {
CtMap.Dither[];
Imager.SetColor[context, ImagerColor.ColorFromRGB[[1.0, 1.0, 0.0]]];
Imager.SetStrokeWidth[context, 1.0];
};
IF NOT forInterpress AND (drawTriangles OR drawPolygons) THEN {
Action: PROC ~ {
ENABLE G3dMatrix.singular => CONTINUE;
SELECT TRUE FROM
drawTriangles AND drawBackFaces => DrawTriangles[
context, surface, view, drawNormals, clipCube, directionSelect, forInterpress, zip];
drawTriangles AND NOT drawBackFaces => DrawFrontFacingTriangles[
context, surface, view, drawNormals, clipCube, directionSelect, forInterpress, zip];
drawPolygons AND drawBackFaces => DrawPolygons[
context, surface, view, drawNormals, clipCube, directionSelect, forInterpress, zip];
drawPolygons AND NOT drawBackFaces => DrawFrontFacingPolygons[
context, surface, view, drawNormals, clipCube, directionSelect, forInterpress, zip];
ENDCASE;
};
WrapInCG6[context, Action];
};
IF drawVertices THEN {
radius: REAL ¬ 0.75;
IF color THEN Imager.SetColor[context, ImagerColor.ColorFromRGB[[1.0, 0.0, 0.0]]];
FOR n: NAT IN[0..surface.vertices.length) DO
Process.CheckForAbort[];
IF NOT drawBackFaces
THEN {
polygonProc: PolygonProc ~ {
FOR i: NAT IN [0..polygon.length) DO
IF polygon[i] = n THEN {
Draw2d.Circle[context, surface.screens[n].pos, radius, TRUE];
EXIT;
};
ENDLOOP;
};
ImplicitPolygons.ApplyToFrontFacingPolygons[surface, view, polygonProc];
}
ELSE Draw2d.Circle[context, surface.screens[n].pos, radius, TRUE];
ENDLOOP;
};
IF labelVertices THEN FOR n: NAT IN[0..surface.vertices.length) DO
Process.CheckForAbort[];
Draw2d.Label[context, surface.screens[n].pos, IO.PutFR["%g", IO.int[n]]];
ENDLOOP;
IF drawCurves THEN {
IF surface.curves = NIL THEN ImplicitSurface.SetSurfaceCurves[surface];
G3dDraw.DrawCurves[context, surface.curves, view, , forInterpress, zip];
};
};
DrawFrontFacingPolygons: PUBLIC PROC [
context: Context,
surface: Surface,
view: Matrix,
drawNormals: BOOL ¬ FALSE,
clipCube: Cube ¬ NIL,
directionSelect: DirectionSelect ¬ xyz,
forInterpress: BOOL ¬ FALSE,
zip: Zip ¬ NIL]
~ {
Note: No perspective clipping!
polygonProc: PolygonProc ~ {
Process.CheckForAbort[];
DrawPolygon[context, surface, polygon, clipCube, directionSelect, forInterpress, zip];
IF drawNormals THEN DrawPolyNormals[context, surface, view, polygon];
};
ImplicitPolygons.ApplyToFrontFacingPolygons[surface, view, polygonProc];
};
DrawFrontFacingTriangles: PUBLIC PROC [
context: Context,
surface: Surface,
view: Matrix,
drawNormals: BOOL ¬ FALSE,
clipCube: Cube ¬ NIL,
directionSelect: DirectionSelect ¬ xyz,
forInterpress: BOOL ¬ FALSE,
zip: Zip ¬ NIL]
~ {
Note: No perspective clipping!
polygonProc: PolygonProc ~ {
Process.CheckForAbort[];
Reverse the sense of the front facing test, since implicit polygons are backwards:
IF nPolygon >= surface.faceNormals.length OR NOT G3dVector.FrontFacingNoPerspective[surface.faceNormals[nPolygon], view] THEN {
i2: NAT ¬ polygon[0];
FOR n: NAT IN [1..polygon.length-2] DO
i0: NAT ¬ polygon[n+1];
i1: NAT ¬ polygon[n];
DrawTriangle[context, surface, i0, i1, i2, clipCube, directionSelect, forInterpress, zip];
ENDLOOP;
IF drawNormals THEN DrawPolyNormals[context, surface, view, polygon];
};
};
IF NOT ImplicitSurface.VerticesOK[surface, view] THEN RETURN;
IF NOT ImplicitSurface.FaceNormalsCentersOK[surface] THEN RETURN;
ImplicitPolygons.ApplyToSurfacePolygons[surface, polygonProc];
};
DrawPolygons: PUBLIC PROC [
context: Context,
surface: Surface,
view: Matrix,
drawNormals: BOOL ¬ FALSE,
clipCube: Cube ¬ NIL,
directionSelect: DirectionSelect ¬ xyz,
forInterpress: BOOL ¬ FALSE,
zip: Zip ¬ NIL]
~ {
Note: No perspective clipping!
polygonProc: PolygonProc ~ {
Process.CheckForAbort[];
DrawPolygon[context, surface, polygon, clipCube, directionSelect, forInterpress, zip];
};
IF NOT ImplicitSurface.VerticesOK[surface, view] THEN RETURN;
ImplicitPolygons.ApplyToSurfacePolygons[surface, polygonProc];
IF drawNormals THEN DrawNormals[context, surface, view];
};
DrawTriangle: PUBLIC PROC [
context: Context,
surface: Surface,
i0, i1, i2: NAT,
clipCube: Cube ¬ NIL,
directionSelect: DirectionSelect ¬ xyz,
forInterpress: BOOL ¬ FALSE,
zip: Zip ¬ NIL]
~ {
p0, p1, p2: Pair;
v0: Vertex ~ surface.vertices[i0];
v1: Vertex ~ surface.vertices[i1];
v2: Vertex ~ surface.vertices[i2];
IF clipCube # NIL THEN {
IF NOT G3dOctree.PointInCube[v0.point, clipCube, 0.05] THEN RETURN;
IF NOT G3dOctree.PointInCube[v1.point, clipCube, 0.05] THEN RETURN;
IF NOT G3dOctree.PointInCube[v2.point, clipCube, 0.05] THEN RETURN;
};
p0 ¬ surface.screens[i0].pos;
p1 ¬ surface.screens[i1].pos;
p2 ¬ surface.screens[i2].pos;
IF forInterpress
THEN {
Imager.SetStrokeJoint[context, round];
Imager.MaskStrokeTrajectory[context, ImagerPath.LineTo[
ImagerPath.LineTo[ImagerPath.MoveTo[p0], p1], p2], TRUE];
}
ELSE {
IF VerticesDirSelected[v0, v1, directionSelect] THEN Line[context, p0, p1];
IF VerticesDirSelected[v1, v2, directionSelect] THEN Line[context, p1, p2];
IF VerticesDirSelected[v2, v0, directionSelect] THEN Line[context, p2, p0];
};
};
DrawNormal: PROC [context: Context, surface: Surface, nVertex: NAT, view: Matrix] ~ {
G3dDraw.DrawVector[
context, surface.vertices[nVertex].point, surface.vertices[nVertex].normal, view,, 0.02];
};
DrawPolyNormals: PROC [context: Context, surface: Surface, view: Matrix, poly: NatSequence]
~ {
FOR n: NAT IN [0..poly.length) DO DrawNormal[context, surface, poly[n], view]; ENDLOOP;
};
DrawNormals: PUBLIC PROC [context: Context, surface: Surface, view: Matrix] ~ {
IF surface.vertices # NIL AND surface.vertexValidities.normal THEN
FOR n: NAT IN [0..surface.vertices.length) DO
DrawNormal[context, surface, n, view];
ENDLOOP;
};
DrawTriangles: PUBLIC PROC [
context: Context,
surface: Surface,
view: Matrix,
drawNormals: BOOL ¬ FALSE,
clipCube: Cube ¬ NIL,
directionSelect: DirectionSelect ¬ xyz,
forInterpress: BOOL ¬ FALSE,
zip: Zip ¬ NIL]
~ {
Note: No perspective clipping!
polygonProc: PolygonProc ~ {
i2: NAT ¬ polygon[0];
Process.CheckForAbort[];
FOR n: NAT IN [1..polygon.length-2] DO
i0: NAT ¬ polygon[n+1];
i1: NAT ¬ polygon[n];
DrawTriangle[context, surface, i0, i1, i2, clipCube, directionSelect, forInterpress, zip];
ENDLOOP;
};
IF NOT ImplicitSurface.VerticesOK[surface, view] THEN RETURN;
ImplicitPolygons.ApplyToSurfacePolygons[surface, polygonProc];
IF drawNormals THEN DrawNormals[context, surface, view];
};