Copyright Ó 1987 by Xerox Corporation. All rights reserved.
Frank Crow, February 15, 1988 3:21:02 pm PST
Quick display lists for lines.
Bloomenthal, September 26, 1988 12:04:42 pm PDT
DIRECTORY
Atom USING [ GetPropFromList, PutPropOnList ],
Real USING [ Fix ],
ImagerBackdoor USING [ AccessBufferRectangle ],
ImagerPixel USING [ PixelMap ],
ScanConvert USING [ PutLine ],
G3dMatrix USING [ Mul ],
ShapeUtilities USING [ ShapePatch, ShapePatchToPatch, XfmPtToEyeSpace ],
ThreeDBasics USING [ Context, Error, GetSurfaceType, ImagerProc, ImagerProcRec,
IntegerPairSequence, NoneOut, OutCode, Patch, PatchProc, Pixel,
PtrPatchSequence, RegisterSurfaceType, ShapeClass,
ShapeInstance, ShapeProc, Triple, TripleSequence, Xfm3D ];
QuickListProcs:
CEDAR
PROGRAM
IMPORTS Atom, ImagerBackdoor, G3dMatrix, Real, ScanConvert, ShapeUtilities, ThreeDBasics
~ BEGIN
Type Definitions
LORA: TYPE ~ LIST OF REF ANY;
PixelMap: TYPE ~ ImagerPixel.PixelMap;
Context: TYPE ~ ThreeDBasics.Context;
Pixel: TYPE ~ ThreeDBasics.Pixel;
Xfm3D: TYPE ~ ThreeDBasics.Xfm3D;
OutCode: TYPE ~ ThreeDBasics.OutCode;
NoneOut: OutCode ~ ThreeDBasics.NoneOut;
ShapePatch: TYPE ~ ShapeUtilities.ShapePatch;
Patch: TYPE ~ ThreeDBasics.Patch;
PatchProc: TYPE ~ ThreeDBasics.PatchProc;
ShapeClass: TYPE ~ ThreeDBasics.ShapeClass;
ShapeInstance: TYPE ~ ThreeDBasics.ShapeInstance;
IntegerPairSequence: TYPE ~ ThreeDBasics.IntegerPairSequence;
Triple: TYPE ~ ThreeDBasics.Triple;
TripleSequence: TYPE ~ ThreeDBasics.TripleSequence;
TripleSeqSequence:
TYPE ~
RECORD[
length: NAT ← 0,
s: SEQUENCE maxLength: CARDINAL OF REF TripleSequence
];
PtrPatchSequence: TYPE ~ ThreeDBasics.PtrPatchSequence;
BoolSequence: TYPE ~ RECORD[ SEQUENCE length: CARDINAL OF BOOLEAN ];
BoolSeqSequence: TYPE ~ RECORD[ SEQUENCE length: CARDINAL OF REF BoolSequence ];
Line Drawings
DoDisplayList: ThreeDBasics.ShapeProc ~ {
PROC[context: REF Context, shape: REF ShapeInstance, data: REF ANY ← NIL]
RETURNS[REF ShapeInstance]
Call this to get through viewer to draw on screen
IF context.viewer #
NIL
-- do through viewer
THEN context.class.drawInViewer[
context, NEW[ThreeDBasics.ImagerProcRec ← [ViewerDisplayList, shape]]
]
ELSE DrawShape[context, shape]; -- do directly
RETURN[shape];
};
ViewerDisplayList: ThreeDBasics.ImagerProc ~ {
PROC[context: REF Context, imagerCtx: Imager.Context, data: REF ANY ← NIL]
This gets pixel map and calls proc which draws lines based on display list
DoIt:
PROC[pixelMap: PixelMap] ~ {
shape: REF ShapeInstance ← NARROW[ data ];
tempPixels: PixelMap ← context.pixels; context.pixels ← pixelMap;
DrawShape[context, shape];
context.pixels ← tempPixels;
};
ImagerBackdoor.AccessBufferRectangle[imagerCtx, DoIt, context.viewPort^];
};
DrawShape:
PROC [ context:
REF Context, shape:
REF ShapeInstance ]
~ {
This acquires display list from shape.props and executes it, calls proc to build list if none
dList: REF ← Atom.GetPropFromList[shape.props, $LinesList];
color: Pixel ← [
Real.Fix[shape.shadingClass.color.R * 255.0],
Real.Fix[shape.shadingClass.color.G * 255.0],
Real.Fix[shape.shadingClass.color.B * 255.0],
0, 0
];
SELECT context.class.displayType
FROM
$PseudoColor =>
color[r] ← 42 * (color[r] * 6 / 256) + 6 * (color[g] * 7 / 256) + (color[b] * 6 / 256) +2;
$Gray => color[r] ← (color[r] + color[g] + color[b]) / 3;
ENDCASE;
IF dList = NIL THEN dList ← MakeDisplayList[context, shape];
IF shape.class.type = $ConvexPolygon
THEN {
list: REF IntegerPairSequence ← NARROW[dList];
FOR i:
NAT
IN [0..list.length)
DO
IF context.stopMe^ THEN RETURN;
ScanConvert.PutLine[ context,
[ Real.Fix[shape.vertex[list[i].x].sx], Real.Fix[shape.vertex[list[i].x].sy] ],
[ Real.Fix[shape.vertex[list[i].y].sx], Real.Fix[shape.vertex[list[i].y].sy] ],
color, color
];
ENDLOOP;
}
ELSE {
-- not polygonal have to transform curved paths
list: REF TripleSeqSequence ← NARROW[dList];
xfm: Xfm3D ← G3dMatrix.Mul[shape.position, context.eyeSpaceXfm];
lsx, lsy: INTEGER;
FOR i:
NAT
IN [0..list.length)
DO
FOR j:
NAT
IN [0..list[i].length)
DO
OPEN list[i][j];
clip: OutCode;
ex, ey, ez, sx, sy: REAL; isx, isy: INTEGER;
[ [ex, ey, ez], clip ] ← ShapeUtilities.XfmPtToEyeSpace[ context, [x, y, z], xfm ];
IF clip # NoneOut
-- oops, ShapeUtilities.XfmToEyeSpace got it wrong
THEN { shape.clipState ← clipped; EXIT; }
ELSE {
sx ← context.eyeToNdc.scaleX * ex / ez + context.eyeToNdc.addX;
sy ← context.eyeToNdc.scaleY * ey / ez + context.eyeToNdc.addY;
isx ← Real.Fix[ context.ndcToPixels.scaleX * sx + context.ndcToPixels.addX ];
isy ← Real.Fix[ context.ndcToPixels.scaleY * sy + context.ndcToPixels.addY ];
IF j > 0 THEN ScanConvert.PutLine[context, [isx, isy], [lsx, lsy], color, color];
lsx ← isx; lsy ← isy;
}
ENDLOOP;
ENDLOOP;
};
};
MakeDisplayList:
PROC [ context:
REF Context, shape:
REF ShapeInstance ]
RETURNS[
REF] ~ {
IF shape.class.type = $ConvexPolygon
THEN RETURN[ MakePolygonDisplayList[context, shape] ]
ELSE RETURN[ MakePatchDisplayList[context, shape] ];
};
MakePolygonDisplayList:
PROC [ context:
REF Context, shape:
REF ShapeInstance ]
RETURNS[
REF] ~ {
Creates display list for line drawings of polygonal object, culls duplicated edges
patches: REF PtrPatchSequence;
size: NAT ← shape.vertex.length;
displayList: REF IntegerPairSequence ← NEW[IntegerPairSequence[3*size]]; -- all triangles makes < 3 edges per vertex
connections: REF BoolSeqSequence ← NEW[BoolSeqSequence[shape.vertex.length]];
c1, c2, count: NAT ← 0;
patches ← NARROW[shape.surface, REF PtrPatchSequence];
FOR i:
NAT
IN (0..shape.vertex.length)
DO
-- fill half matrix less diagonal with FALSE
connections[i] ← NEW[ BoolSequence[i] ];
FOR j: NAT IN [0..i) DO connections[i][j] ← FALSE; ENDLOOP;
ENDLOOP;
FOR i:
NAT
IN [0..shape.numSurfaces)
DO
IF shape.class.type # $ConvexPolygon
THEN SIGNAL ThreeDBasics.Error[[$MisMatch, "Operation only for convex polygons"]]
ELSE
FOR j:
NAT
IN [0..patches[i].nVtces]
DO
k: NAT ← IF j = patches[i].nVtces THEN 0 ELSE j;
c2 ← patches[i].vtxPtr[k];
IF j > 0
THEN {
IF c1 > c2
THEN
IF connections[c1][c2] =
FALSE
THEN {
displayList[count] ← [c1, c2]; count ← count + 1;
connections[c1][c2] ← TRUE;
};
IF c2 > c1
THEN
IF connections[c2][c1] =
FALSE
THEN {
displayList[count] ← [c2, c1]; count ← count + 1;
connections[c2][c1] ← TRUE;
};
};
c1 ← c2;
ENDLOOP;
ENDLOOP;
displayList.length ← count;
shape.props ← Atom.PutPropOnList[shape.props, $LinesList, displayList];
RETURN[displayList];
};
tol: REAL ← .001; -- tolerance for endpoint matching
GrabEdges: PatchProc ~ {
PROC[context: REF Context, patch: REF Patch, data: REF ANY ← NIL] RETURNS[REF Patch]
Used to temporarily replace polygon rendering proc in context, captures calls and culls duplicates, stores result in display list
shape: REF ShapeInstance ← NARROW[ Atom.GetPropFromList[patch.props, $Shape] ];
displayList:
REF TripleSeqSequence ←
NARROW[
Atom.GetPropFromList[shape.props, $LinesList]
];
FOR i:
NAT
IN [0..displayList.length)
DO
OPEN patch[patch.nVtces-1].coord;
pt: Triple ← displayList[i][0]; -- get first point in sequence
IF
ABS[pt.x - x] < tol
AND
ABS[pt.y - y] < tol
AND
ABS[pt.z - z] < tol
THEN {
OPEN patch[0].coord; -- opposite endpoints match, try other ends
pt: Triple ← displayList[i][displayList[i].length-1]; -- get last point in sequence
IF
ABS[pt.x - x] < tol
AND
ABS[pt.y - y] < tol
AND
ABS[pt.z - z] < tol
THEN {
OPEN patch[patch.nVtces/2].coord; -- check middle points
pt: Triple ← displayList[i][displayList[i].length - 1 - patch.nVtces/2];
IF
ABS[pt.x - x] < tol
AND
ABS[pt.y - y] < tol
AND
ABS[pt.z - z] < tol
THEN
RETURN[patch]; -- both ends and middle match, line stored in other direction
};
};
pt ← displayList[i][displayList[i].length-1];
IF
ABS[pt.x - x] < tol
AND
ABS[pt.y - y] < tol
AND
ABS[pt.z - z] < tol
THEN {
OPEN patch[0].coord; -- last endpoints match, try other end
pt: Triple ← displayList[i][0]; -- get first point in sequence
IF
ABS[pt.x - x] < tol
AND
ABS[pt.y - y] < tol
AND
ABS[pt.z - z] < tol
THEN {
OPEN patch[patch.nVtces/2].coord; -- check middle points
pt: Triple ← displayList[i][patch.nVtces/2];
IF
ABS[pt.x - x] < tol
AND
ABS[pt.y - y] < tol
AND
ABS[pt.z - z] < tol
THEN
RETURN[patch]; -- both ends and middle match, line stored in other direction
};
};
ENDLOOP;
IF displayList.length = displayList.maxLength
THEN {
-- extend display list
newList:
REF TripleSeqSequence ←
NEW[
TripleSeqSequence[displayList.length + shape.vertex.length]
];
FOR i: NAT IN [0..displayList.length) DO newList[i] ← displayList[i] ENDLOOP;
newList.length ← displayList.length;
displayList ← newList;
};
displayList[displayList.length] ← NEW[TripleSequence[patch.nVtces]]; -- add new edge
FOR i:
NAT
IN [0..patch.nVtces)
DO
displayList[displayList.length][i] ← [ patch[i].coord.x, patch[i].coord.y, patch[i].coord.z ];
ENDLOOP;
displayList[displayList.length].length ← patch.nVtces;
displayList.length ← displayList.length + 1;
RETURN[patch];
};
MakePatchDisplayList:
PROC [ context:
REF Context, shape:
REF ShapeInstance ]
RETURNS[
REF] ~ {
Creates display list for line drawings of patch shape by replacing polygon display proc with GrabEdges then calling for display of all patches of shape to capture the resulting polygon calls
patches: REF PtrPatchSequence;
size: NAT ← shape.vertex.length;
displayList: REF TripleSeqSequence ← NEW[TripleSeqSequence[3*size]]; -- max. for triangles
tempProc: PatchProc ← context.class.displayPolygon;
context.class.displayPolygon ← GrabEdges; -- ambush polygon display proc
shape.props ← Atom.PutPropOnList[shape.props, $LinesList, displayList];
patches ← NARROW[shape.surface, REF PtrPatchSequence];
FOR i:
NAT
IN [0..shape.numSurfaces)
DO
IF patches[i] #
NIL
THEN {
patch:
REF Patch ← ShapeUtilities.ShapePatchToPatch[
context, NEW[ ShapePatch ← [shape, i, 0, 0, 0.0] ]
];
[] ← shape.class.displayPatch[ context, patch ];
};
ENDLOOP;
context.class.displayPolygon ← tempProc; -- restore polygon display proc
RETURN[displayList];
};