Types
ROPE: TYPE ~ Rope.ROPE;
NatSequence: TYPE ~ G3dRender.NatSequence;
NatSequenceRep: TYPE ~ G3dRender.NatSequenceRep;
Pair: TYPE ~ G3dRender.Pair;
Triple: TYPE ~ G3dRender.Triple;
TripleSequence: TYPE ~ G3dRender.TripleSequence;
TripleSequenceRep: TYPE ~ G3dBasic.TripleSequenceRep;
RGB: TYPE ~ G3dRender.RGB;
RealSequence: TYPE ~ G3dRender.RealSequence;
RealSequenceRep: TYPE ~ G3dBasic.RealSequenceRep;
Context: TYPE ~ G3dRender.Context;
SixSides: TYPE ~ G3dRender.SixSides;
Matrix: TYPE ~ G3dRender.Matrix;
Shape: TYPE ~ G3dRender.Shape;
Patch: TYPE ~ G3dRender.Patch;
PatchSequence: TYPE ~ G3dRender.PatchSequence;
PatchSequenceRep: TYPE ~ G3dRender.PatchSequenceRep;
PatchProc: TYPE ~ G3dRender.PatchProc;
Vertex: TYPE ~ G3dShape.Vertex;
CtlPoint: TYPE ~ G3dRender.CtlPoint;
CtlPtInfo:
TYPE ~ G3dRender.CtlPtInfo;
RECORD[coord: CtlPoint, shade: Shading, props: Atom.PropList, aux: REF ANY];
CtlPtInfoSequence: TYPE ~ G3dRender.CtlPtInfoSequence;
CtlPtInfoProc: TYPE ~ G3dRender.CtlPtInfoProc;
Shading: TYPE ~ G3dRender.Shading;
RenderData: TYPE ~ G3dRender.RenderData;
RenderStyle: TYPE ~ G3dRender.RenderStyle;
ShapeClass: TYPE ~ G3dRender.ShapeClass;
ShapeProc: TYPE ~ G3dRender.ShapeProc;
ClipState: TYPE ~ G3dRender.ClipState;
OutCode: TYPE ~ G3dRender.OutCode;
AllOut: OutCode ~ G3dRender.AllOut;
NoneOut: OutCode ~ G3dRender.NoneOut;
FacingDir: TYPE ~ G3dRender.FacingDir;
LORA: TYPE = LIST OF REF ANY;
MidPtProc: TYPE ~ PROC[v0, v1: REF CtlPtInfo] RETURNS[REF CtlPtInfo];
nullTriple: Triple ~ [0.0, 0.0, 0.0];
Corner:
TYPE ~
RECORD [ inVtx, outVtx, ptr:
NAT ← 0,
inDir, outDir, normal, interiorKnot, interiorKnot2: Triple ← nullTriple,
double:
BOOLEAN ←
FALSE ];
Represents a corner of a polygon,
- inVtx is the vertex at the other end of the incoming edge (previous vertex in order)
- outVtx is other vertex on outgoing edge
- ptr is multipurpose marker, sometimes the vtx number, sometimes the patch number
- inDir, outDir are the corresponding outward direction vectors, inDir lies clockwise of outDir (later used as Bezier knots)
- normal is the carefully determined normal vector
- interiorKnot is the interior Bezier patch control point between inDir and outDir
- interiorKnot2 is the 2nd interior ctl. pt. for a doubled corner, lies between interiorKnot and outDir
- Double = TRUE indicates corner is treated as a degenerate edge needing a double interior control point when treated as a Bezier patch.
CornerSeq: TYPE ~ RECORD [ length: NAT ← 0, s: SEQUENCE maxLength: NAT OF Corner ];
CornerSeqSeq: TYPE ~ RECORD [ length: NAT ← 0,
s: SEQUENCE maxLength: NAT OF REF CornerSeq ];
TangentSet:
TYPE ~
RECORD [t0, et0, t1, et1: Triple ← nullTriple];
Represents the tangents at the endpoints of an edge (in object space and eyespace), the edge is ordered in the vertex order of the polygon (t0 at leading endpoint, t1 at trailing endpoint)
TangentSeq: TYPE ~ RECORD [length: NAT ← 0, s: SEQUENCE maxLength: NAT OF TangentSet];
TangentTriple: TYPE ~ ARRAY [0..3) OF TangentSet;
TangentSeqSeq:
TYPE ~
RECORD [
length: NAT ← 0, s: SEQUENCE maxLength: NAT OF REF TangentSeq];
Triangle: TYPE ~ RECORD [ v: ARRAY[0..3) OF CtlPtInfo, t: ARRAY[0..3) OF TangentSet ];
NatSequenceSequence: TYPE ~ RECORD [
length: NAT ← 0, s: SEQUENCE maxLength: NAT OF NatSequence ];
Renamed Procedures
Add: PROC[v1, v2: Triple] RETURNS[Triple] ~ G3dVector.Add;
Cross: PROC[v1, v2: Triple] RETURNS[Triple] ~ G3dVector.Cross;
Dot: PROC[v1, v2: Triple] RETURNS[REAL] ~ G3dVector.Dot;
Length: PROC[v: Triple] RETURNS[REAL] ~ G3dVector.Length;
Negate: PROC[v: Triple] RETURNS[Triple] ~ G3dVector.Negate;
Normalize: PROC[v: Triple] RETURNS[Triple] ~ G3dVector.Normalize;
Sub3: PROC[v1, v2: Triple] RETURNS[Triple] ~ G3dVector.Sub;
ReleasePatch: PROC [p: REF Patch] ~ G3dClipXfmShade.ReleasePatch;
GetPatch: PROC [size: NAT] RETURNS [REF Patch] ~ G3dClipXfmShade.GetPatch;
GetProp: PROC [propList: Atom.PropList, prop: REF ANY] RETURNS [REF ANY] ~
Atom.GetPropFromList;
PutProp: PROC [propList: Atom.PropList, prop: REF ANY, val: REF ANY]
RETURNS [Atom.PropList] ~ Atom.PutPropOnList;
Utility Procedures
Sqr:
PROCEDURE [number:
REAL]
RETURNS [
REAL] ~
INLINE {
RETURN[number * number]; };
Sub:
PROC[f, g:
REAL]
RETURNS[
REAL] ~ {
Difference f - g, returns zero if less than 3 decimal places
IF RealFns.AlmostEqual[f, g, -10] THEN RETURN [0.0] ELSE RETURN[f-g];
};
Sub1:
PROC[f, g:
REAL]
RETURNS[
REAL] ~ {
Screen space f - g, returns zero if less than noticeable
result: REAL ← f-g;
IF ABS[result] < G3dScanConvert.justNoticeable THEN RETURN [0.0] ELSE RETURN[result];
};
DiffPosns:
PROC[vtx1, vtx2: CtlPoint, space:
ATOM ←
NIL]
RETURNS[Triple] ~ {
Subtracts vtx2 from vtx1 in selected space
SELECT space
FROM
$Eye => RETURN[[Sub[vtx1.ex, vtx2.ex], Sub[vtx1.ey, vtx2.ey], Sub[vtx1.ez, vtx2.ez]]];
$Screen=> RETURN[[Sub1[vtx1.sx, vtx2.sx], Sub1[vtx1.sy, vtx2.sy], Sub1[vtx1.sz, vtx2.sz]]];
ENDCASE =>
-- object space
RETURN[[Sub[vtx1.x, vtx2.x], Sub[vtx1.y, vtx2.y], Sub[vtx1.z, vtx2.z]]];
};
ExtendCornerSeq:
PROC[corners:
REF CornerSeq]
RETURNS[newCorners:
REF CornerSeq] ~ {
newCorners ← NEW[CornerSeq[corners.maxLength+4]];
FOR i: NAT IN [0..corners.maxLength) DO newCorners[i] ← corners[i]; ENDLOOP;
newCorners.length ← corners.length;
};
ShowCorner:
PROC[corner:
REF CornerSeq, keys:
LIST
OF
ROPE]
RETURNS[
ROPE] ~ {
AddNat:
PROC[number:
NAT] ~ {
msg ← Rope.Cat[msg, ", ", Convert.RopeFromInt[number] ];
};
AddTriple:
PROC[trio: Triple] ~ {
msg ← Rope.Cat[ msg, ", ", Convert.RopeFromReal[Real.Fix[trio.x*100.0] / 100.0 ] ];
msg ← Rope.Cat[ msg, ", ",
Convert.RopeFromReal[ Real.Fix[trio.y*100.0] / 100.0 ], ", ",
Convert.RopeFromReal[ Real.Fix[trio.z*100.0] / 100.0 ]
];
};
msg: ROPE;
FOR i:
NAT
IN [0..corner.length)
DO
FOR list:
LIST
OF
ROPE ← keys, list.rest
UNTIL list =
NIL
DO
SELECT
TRUE
FROM
Rope.Equal[list.first, "inVtx", FALSE] => AddNat[corner[i].inVtx];
Rope.Equal[list.first, "outVtx", FALSE] => AddNat[corner[i].outVtx];
Rope.Equal[list.first, "ptr", FALSE] => AddNat[corner[i].ptr];
Rope.Equal[list.first, "inDir", FALSE] => AddTriple[corner[i].inDir];
Rope.Equal[list.first, "outDir", FALSE] => AddTriple[corner[i].outDir];
Rope.Equal[list.first, "normal", FALSE] => AddTriple[corner[i].normal];
Rope.Equal[list.first, "interiorKnot", FALSE] => AddTriple[corner[i].interiorKnot];
Rope.Equal[list.first, "interiorKnot2", FALSE] => AddTriple[corner[i].interiorKnot2];
Rope.Equal[list.first, "double",
FALSE] => msg ← Rope.Cat[
msg, ", ", IF corner[i].double THEN "TRUE" ELSE "FALSE"
];
ENDCASE;
ENDLOOP;
msg ← Rope.Concat[msg, "\n"];
ENDLOOP;
RETURN[ msg ];
};
ShowCoords:
PROC[poly:
REF Patch, space:
ATOM ← $Screen]
RETURNS[list:
LIST
OF
REF Pair] ~ {
FOR i:
CARD16
DECREASING
IN [0..poly.nVtces)
DO
p: REF Pair;
SELECT space
FROM
$Screen => p ← NEW[ Pair ← [ poly[i].coord.sx, poly[i].coord.sy ] ];
$Eye => p ← NEW[ Pair ← [ poly[i].coord.ex, poly[i].coord.ey ] ];
$Object => p ← NEW[ Pair ← [ poly[i].coord.x, poly[i].coord.y ] ];
ENDCASE;
list ← CONS[p, list];
ENDLOOP;
RETURN[list];
};
GetSlopeVec:
PROC[normal, edge: Triple, hermite:
BOOL ←
FALSE]
RETURNS[slope: Triple] ~ {
Returns a vector normal to the 1st vector and in the plane defined by both vectors
Magnitude is scaled to to proper length for Bezier inner control pt approximating circular arc
slope ← Cross[ Cross[normal, edge], normal ];
slope ← ScaleTangent[ slope, edge ];
};
ScaleTangent:
PROC[tangent, edgeDir: Triple]
RETURNS[Triple] ~ {
Scale tangent vector to proper length for Bezier inner control pt approximating circular arc
adjSide, oppSide, scale: REAL;
edgeLength: REAL ← Length[edgeDir];
hypotenuse: REAL ← Length[tangent];
IF edgeLength = 0.0 OR hypotenuse = 0.0 THEN RETURN [[0.0, 0.0, 0.0]];
adjSide ← ABS[Dot[edgeDir, tangent] / edgeLength];
oppSide ←
IF adjSide >= hypotenuse
THEN 0.0
ELSE RealFns.SqRt[hypotenuse*hypotenuse - adjSide*adjSide];
scale ←
IF oppSide/hypotenuse > .01
THEN edgeLength * 2.0 * (hypotenuse - adjSide) / (3.0 * oppSide * oppSide)
ELSE .333333 * edgeLength / hypotenuse;
RETURN[ G3dVector.Mul[ tangent, scale ] ];
};
PatchSort:
PROC[ context: Context, p: PatchSequence, c:
REF CornerSeqSeq ←
NIL]
RETURNS[PatchSequence,
REF CornerSeqSeq] ~ {
z: RealSequence ← NEW[RealSequenceRep[p.length]];
pOut: PatchSequence ← NEW [PatchSequenceRep[p.length]];
cOut:
REF CornerSeqSeq ←
NEW [CornerSeqSeq[p.length]];
Get average of depths at corners
FOR i:
NAT
IN [0..p.length)
DO
z[i] ← 0.0;
FOR j: NAT IN [0..p[i].nVtces) DO z[i] ← z[i] + p[i][j].coord.ez; ENDLOOP;
z[i] ← z[i] / p[i].nVtces;
pOut[i] ← p[i]; cOut[i] ← c[i];
ENDLOOP;
FOR i:
NAT
IN [1..p.length)
DO
FOR j:
NAT
DECREASING
IN [0..i)
DO
-- sort to increasing depth order
IF z[j+1] < z[j]
THEN {
t: REAL ← z[j+1]; p: REF Patch ← pOut[j+1]; c: REF CornerSeq ← cOut[j+1];
z[j+1] ← z[j]; pOut[j+1] ← pOut[j]; cOut[j+1] ← cOut[j];
z[j] ← t; pOut[j] ← p; cOut[j] ← c;
};
ENDLOOP;
ENDLOOP;
IF
NOT context.antiAliasing
THEN
FOR i:
NAT
IN [0..p.length/2)
DO
-- re-order back-to-front
j: NAT ← p.length-1 - i;
tmpP: REF Patch ← pOut[i]; tmpC: REF CornerSeq ← cOut[i];
pOut[i] ← pOut[j]; cOut[i] ← cOut[j];
pOut[j] ← tmpP; cOut[j] ← tmpC;
ENDLOOP;
pOut.length ← p.length;
RETURN[pOut, cOut];
};
Intersection:
PROC[pos1, pos2, dir1, dir2, normal: Triple]
RETURNS [pt: Triple] ~ {
Intersect2d:
PROC[ pos1, dir1, pos2, dir2: Pair ]
RETURNS[ pos: Pair ]~ {
l1: Triple ← G3dVector.Line2d[ pos1, [pos1.x + dir1.x, pos1.y + dir1.y] ];
l2: Triple ← G3dVector.Line2d[ pos2, [pos2.x + dir2.x, pos2.y + dir2.y] ];
pos ← G3dVector.IntersectTwoLines2d[l1, l2];
};
n: Triple ← normal;
pr: Pair;
SELECT
TRUE
FROM
ABS[n.x] >=
ABS[n.y]
AND
ABS[n.x] >=
ABS[n.z] => {
pr ← Intersect2d[ [pos1.y, pos1.z], [dir1.y, dir1.z], [pos2.y, pos2.z], [dir2.y, dir2.z] ];
pt ← [ -(n.y*pr.x + n.z*pr.y)/n.x, pr.x, pr.y ];
};
ABS[n.y] >=
ABS[n.z]
AND
ABS[n.y] >=
ABS[n.x] => {
pr ← Intersect2d[ [pos1.z, pos1.x], [dir1.z, dir1.x], [pos2.z, pos2.x], [dir2.z, dir2.x] ];
pt ← [ pr.y, -(n.z*pr.x + n.x*pr.y)/n.y, pr.x ];
};
ABS[n.z] >=
ABS[n.x]
AND
ABS[n.z] >=
ABS[n.y] => {
pr ← Intersect2d[ [pos1.x, pos1.y], [dir1.x, dir1.y], [pos2.x, pos2.y], [dir2.x, dir2.y] ];
pt ← [ pr.x, pr.y, -(n.x*pr.x + n.y*pr.y)/n.z ];
};
ENDCASE;
};
Procedures for conversion of non-planar polygons to Bezier patches
DisplayPatchBezier: PatchProc ~ {
patchNo: NAT ← NARROW[ Atom.GetPropFromList[patch.props, $PatchNo], REF NAT ]^;
corners: REF CornerSeqSeq ← NARROW[ GetProp[patch.renderData.props, $PatchCorners] ];
patch.type ← $PolygonToBezier;
ConvertPolygonToBezier[context, patch, corners[patchNo] ]; -- convert to patch, display
RETURN[ NIL ];
};
ValidatePolyToBezier: ShapeProc ~ {
PROC[context: Context, shape: Shape, data: REF] RETURNS[Shape];
shape ← G3dSortandDisplay.ValidatePolyhedron[context, shape]; -- Do shading and matrices
IF GetProp[G3dRender.RenderDataFrom[shape].props, $PatchCorners] =
NIL
THEN shape ← GetTangents[context, shape]; -- calculate tangent vectors if not read in
RETURN[ shape ];
};
GetEdgeCurveBez:
PROC[p1, p2: CtlPtInfo, c1, c2: Corner]
RETURNS[coeffs: G3dSpline.Coeffs] ~ {
b0, b1, b2, b3: Triple;
[b0, b1, b2, b3] ← CrnrsToBezKnots[ p1, p2, c1, c2 ];
coeffs ← G3dSpline.CoeffsFromBezier[ [b0, b1, b2, b3] ];
};
CrnrsToBezKnots:
PROC[p1, p2: CtlPtInfo, c1, c2: Corner]
RETURNS[b0, b1, b2, b3: Triple] ~ {
Convert endpoints with corners to Bezier knots
edgeDir: Triple;
b0 ← [ p1.coord.x, p1.coord.y, p1.coord.z ];
b3 ← [ p2.coord.x, p2.coord.y, p2.coord.z ];
edgeDir ← Sub3[b3, b0];
b1 ← Add[ b0, c1.outDir ];
b2 ← Add[ b3, c2.inDir ];
b1 ← Add[ b0, ScaleTangent[c1.outDir, edgeDir] ];
b2 ← Add[
b3,
ScaleTangent[c2.inDir, G3dVector.Negate[edgeDir]]
];
};
XfmAndClip:
PROC[context: Context, patch:
REF Patch] ~ {
Transform to eyespace and get clip state
shape: Shape ← NARROW[ Atom.GetPropFromList[patch.props, $Shape] ];
xfm: Matrix ← G3dMatrix.Mul[shape.matrix, context.eyeSpaceXfm];
FOR i:
NAT
IN [0..patch.nVtces)
DO
OPEN patch[i].coord;
[[ ex, ey, ez]] ← G3dMatrix.Transform[ [x, y, z], xfm ];
clip ← G3dClipXfmShade.GetClipCodeForPt[context, [ ex, ey, ez] ];
IF clip = NoneOut
THEN [ [sx, sy, sz] ] ← G3dClipXfmShade.XfmPtToDisplay[ context, [ex, ey, ez], shape ];
ENDLOOP;
};
ConvertPolygonToBezier:
PROC[ context: Context, patch:
REF Patch,
corner:
REF CornerSeq ] ~ {
Converts polygon with corner tangents and interior points into bezier patch
renderStyle: RenderStyle;
IF corner.length > 4 THEN { SliceUpBezier[ context, patch, corner ]; RETURN[]; };
WITH patch.renderData.shadingClass.renderMethod
SELECT
FROM
style:
REF RenderStyle => {
renderStyle ← style^;
SELECT renderStyle
FROM
lines => { [] ← DisplayPatchEdges[context, patch, corner]; RETURN[]; };
ENDCASE;
};
ENDCASE;
IF patch.nVtces = 3
THEN DisplayTriangleAsBezier[ context, patch, corner ]
THEN DisplayTriangleWithTangents[ context, patch, corner ]
ELSE DisplayQuadrilateralAsBezier[ context, patch, corner ];
};
SliceUpBezier:
PROC[ context: Context, patch:
REF Patch,
corners:
REF CornerSeq ] ~ {
outPatch: PatchSequence ← NEW [PatchSequenceRep[(corners.length)/2]]; -- upper bound
outCorner: REF CornerSeqSeq ← NEW [CornerSeqSeq[(corners.length)/2]];
lVtx: NAT ← patch.nVtces-1;
newStart: LIST OF NAT ← LIST[0];
WHILE newStart #
NIL
DO
cVtx, startVtx, lVtx, cCrnr, vtxCnt: NAT;
onPath: BOOLEAN ← TRUE;
pCnt: NAT ← outPatch.length;
outPatch[pCnt] ← GetPatch[4]; -- released by display action
outCorner[pCnt] ← NEW[CornerSeq[4]];
outPatch[pCnt].type ← patch.type;
outPatch[pCnt].oneSided ← patch.oneSided;
outPatch[pCnt].clipState ← patch.clipState;
outPatch[pCnt].dir ← unknown;
outPatch[pCnt].props ← patch.props;
cCrnr ← newStart.first; newStart ← newStart.rest;
startVtx ← cVtx ← corners[cCrnr].ptr; lVtx ← corners[cCrnr].inVtx;
vtxCnt ← 0;
WHILE
TRUE
DO
IF corners[cCrnr].ptr # cVtx
OR corners[cCrnr].inVtx # lVtx
THEN {
IF onPath THEN newStart ← CONS[cCrnr, newStart]; -- not part of current chain
onPath ← FALSE; cCrnr ← cCrnr + 1; -- stack for later processing
}
ELSE {
outPatch[pCnt][vtxCnt] ← patch[cVtx];
outCorner[pCnt][vtxCnt] ← corners[ cCrnr ];
vtxCnt ← vtxCnt + 1; onPath ← TRUE;
lVtx ← cVtx; cVtx ← corners[cCrnr].outVtx; -- step to next vertex
cCrnr ← cCrnr + 1; -- step to next corner
IF cVtx = startVtx THEN EXIT;
};
ENDLOOP;
outPatch[pCnt].nVtces ← vtxCnt;
outCorner[pCnt].length ← vtxCnt;
outPatch.length ← outPatch.length + 1;
ENDLOOP;
[outPatch, outCorner] ← PatchSort[context, outPatch, outCorner]; -- sort to depth order
FOR i:
NAT
IN [0..outPatch.length)
DO
ConvertPolygonToBezier[ context, outPatch[i], outCorner[i] ]; -- convert to patch, display
ReleasePatch[outPatch[i]];
ENDLOOP;
};
DisplayTriangleWithTangents:
PROC[ context: Context, patch:
REF Patch,
corner:
REF CornerSeq ] ~ {
tanClass: ShapeClass;
tangents: REF TangentSeq ← NEW[TangentSeq[3]];
shape: Shape ← NARROW[ GetProp[patch.props, $Shape] ];
xfm: Matrix ← G3dMatrix.Mul[shape.matrix, context.eyeSpaceXfm];
FOR i:
NAT
IN [0..3)
DO
tangents[i].t0 ← corner[i].outDir;
tangents[i].t1 ← corner[(i+1) MOD 3].inDir;
[ tangents[i].et0 ] ← G3dMatrix.TransformVec[ tangents[i].t0, xfm];
[ tangents[i].et1 ] ← G3dMatrix.TransformVec[ tangents[i].t1, xfm];
ENDLOOP;
XfmAndClip[context, patch]; -- transform to eyespace and get clip state
tanClass ← G3dRender.GetShapeClass[ $PolygonWithTangents ];
patch ← tanClass.displayPatch[ context, patch, tangents ];
};
DisplayTriangleAsBezier:
PROC[ context: Context, patch:
REF Patch,
corner:
REF CornerSeq ] ~ {
doubleCornerFound: BOOLEAN ← FALSE;
p: REF Patch ← GetPatch[4];
c: REF CornerSeq ← NEW[CornerSeq[4]];
cVtx: NAT ← 0;
FOR i:
NAT
IN [0..3)
DO
IF
NOT corner[i].double
AND (i < 2
OR doubleCornerFound)
THEN { p[cVtx] ← patch[i]; c[cVtx] ← corner[i]; cVtx ← cVtx+1; }
ELSE {
edge: Triple ← Sub3[ corner[i].outDir, corner[i].inDir ];
IF i = 2
AND
NOT corner[i].double
THEN SIGNAL G3dRender.Error[$MisMatch, "triangle without doubled vertex"];
p[cVtx+1] ← p[cVtx] ← patch[i];
c[cVtx+1] ← c[cVtx] ← corner[i];
c[cVtx].outVtx ← LAST[NAT]; c[cVtx+1].inVtx ← LAST[NAT];
c[cVtx].outDir ← [0.0, 0.0, 0.0]; c[cVtx+1].inDir ← [0.0, 0.0, 0.0];
c[cVtx].double ← FALSE; c[cVtx+1].double ← FALSE;
c[cVtx+1].interiorKnot ← c[cVtx].interiorKnot2;
cVtx ← cVtx+2;
IF
NOT doubleCornerFound
THEN doubleCornerFound ← TRUE
ELSE SIGNAL G3dRender.Error[$MisMatch, "extra doubled vertex"];
};
ENDLOOP;
p.type ← patch.type;
p.oneSided ← patch.oneSided;
p.nVtces ← 4;
p.clipState ← patch.clipState;
p.dir ← unknown;
p.renderData ← patch.renderData;
p.props ← patch.props;
DisplayQuadrilateralAsBezier[ context, p, c ]; ReleasePatch[p];
};
DisplayQuadrilateralAsBezier:
PROC[ context: Context, patch:
REF Patch,
corner:
REF CornerSeq ] ~ {
Build patch boundary by evaluating polygon edges with tangents
Polygons taken clockwise: Patches taken rowwise:
3 -> 0 3 -> 0 3 2 1 0
^ ^ 7 6 5 4
2 <- 1 15 <- 12 11 10 9 8
15 14 13 12
b: REF Patch ← GetPatch[16];
bezClass: ShapeClass;
FOR i:
NAT
IN [0..4)
DO
IF corner[i].double
THEN SIGNAL G3dRender.Error[$MisMatch, "extra doubled vertex"];
ENDLOOP;
[b[0], b[4], b[8], b[12]] ← BoundaryRow[ context, patch[0], patch[1], corner[0], corner[1] ];
[b[12],b[13],b[14],b[15]] ← BoundaryRow[ context, patch[1], patch[2], corner[1], corner[2] ];
[b[15],b[11],b[7], b[3]] ← BoundaryRow[ context, patch[2], patch[3], corner[2], corner[3] ];
[b[3], b[2], b[1], b[0]] ← BoundaryRow[ context, patch[3], patch[0], corner[3], corner[0] ];
Build interior knots by completing parallelograms formed by boundary knots at corners
b[5] ← InteriorPt[ context, b[0], b[1], b[4], corner[0] ];
b[9] ← InteriorPt[ context, b[12], b[13], b[8], corner[1] ];
b[10] ← InteriorPt[ context, b[15], b[14], b[11], corner[2] ];
b[6] ← InteriorPt[ context, b[3], b[2], b[7], corner[3] ];
b.type ← $Bezier;
b.oneSided ← patch.oneSided;
b.nVtces ← 16;
b.clipState ← patch.clipState;
b.dir ← unknown;
b.renderData ← patch.renderData;
b.props ← patch.props;
XfmAndClip[context, b]; -- transform to eyespace and get clip state
bezClass ← G3dRender.GetShapeClass[ $Bezier ];
b ← bezClass.displayPatch[ context, b ]; ReleasePatch[b];
};
BoundaryRow:
PROC[ context: Context, p1, p2: CtlPtInfo, c1, c2: Corner ]
RETURNS[v0, v1, v2, v3: CtlPtInfo] ~ {
Calculates four vertices to use as knots along boundary of patch
InnerShades:
PROC[ s0, s3: Shading ]
RETURNS[ s1, s2: Shading ] ~ {
s1.r ← (2*s0.r + s3.r)/3; s1.g ← (2*s0.g + s3.g)/3; s1.b ← (2*s0.b + s3.b)/3;
s2.r ← (s0.r + 2*s3.r)/3; s2.g ← (s0.g + 2*s3.g)/3; s2.b ← (s0.b + 2*s3.b)/3;
s1.t ← (2*s0.t + s3.t)/3; s2.t ← (s0.t + 2*s3.t)/3;
s1.txtrX ← (2*s0.txtrX + s3.txtrX)/3; s2.txtrX ← (s0.txtrX + 2*s3.txtrX)/3;
s1.txtrY ← (2*s0.txtrY + s3.txtrY)/3; s2.txtrY ← (s0.txtrY + 2*s3.txtrY)/3;
};
b0, b1, b2, b3: Triple;
[b0, b1, b2, b3] ← CrnrsToBezKnots[ p1, p2, c1, c2 ];
v0 ← p1; v3 ← p2;
v1.coord.x ← b1.x; v1.coord.y ← b1.y; v1.coord.z ← b1.z;
v2.coord.x ← b2.x; v2.coord.y ← b2.y; v2.coord.z ← b2.z;
[v1.shade, v2.shade] ← InnerShades[v0.shade, v3.shade];
v1.data ← v2.data ← p1.data;
};
InteriorPt:
PROC[ context: Context, cornerPt, adj1, adj2: CtlPtInfo, corner: Corner ]
RETURNS[ interiorPt: CtlPtInfo ] ~ {
Gets interior point from corner data derives shading data
interiorPt.coord.x ← cornerPt.coord.x + corner.interiorKnot.x;
interiorPt.coord.y ← cornerPt.coord.y + corner.interiorKnot.y;
interiorPt.coord.z ← cornerPt.coord.z + corner.interiorKnot.z;
interiorPt.shade.r ← adj1.shade.r + adj2.shade.r - cornerPt.shade.r;
interiorPt.shade.g ← adj1.shade.g + adj2.shade.g - cornerPt.shade.g;
interiorPt.shade.b ← adj1.shade.b + adj2.shade.b - cornerPt.shade.b;
interiorPt.shade.t ← adj1.shade.t + adj2.shade.t - cornerPt.shade.t;
interiorPt.shade.txtrX ← adj1.shade.txtrX + adj2.shade.txtrX - cornerPt.shade.txtrX;
interiorPt.shade.txtrY ← adj1.shade.txtrY + adj2.shade.txtrY - cornerPt.shade.txtrY;
interiorPt.data ← cornerPt.data;
};
BuildBezierData:
PROC[ shape: Shape, corners:
REF CornerSeqSeq ] ~ {
polyCorners: REF CornerSeqSeq ← NEW[ CornerSeqSeq[shape.surfaces.length] ];
renderData: REF RenderData ← G3dRender.RenderDataFrom[shape];
FOR i:
NAT
IN [0..corners.length)
DO
-- Add inner knots at corners
IF corners[i] # NIL THEN BuildInteriorKnots[ corners[i] ];
ENDLOOP;
FOR i:
NAT
IN [0..corners.length)
DO
IF corners[i] #
NIL
THEN
-- zero for use in next loop
FOR j: NAT IN [0..corners[i].length) DO corners[i][j].ptr ← 0; ENDLOOP;
ENDLOOP;
IF fixDihedrals THEN CheckDihedrals[ shape, corners ]; -- Fix mid-rectangle dihedral angle on each edge
- Adjust rectangles with excessive angles, recheck effected neighbors.
Build Polygon corner structure from vertex corner structure
CtlPoint Corner structure - outVtx matches previous inVtx
Polygon corner structure - outVtx matches next inVtx
FOR i:
NAT
IN [0..shape.surfaces.length)
DO
IF shape.surfaces[i] #
NIL
THEN {
vtxCnt: NAT ← 0;
nVtces: NAT ← shape.surfaces[i].length;
polyCorners[i] ← NEW[CornerSeq[nVtces+2]]; -- allow for one split in polygon
FOR cVtx:
NAT
IN [0..nVtces)
DO
-- current vertex in polygon
nextVtx: NAT ← (cVtx + 1) MOD nVtces;
prevVtx: NAT ← (cVtx + nVtces-1) MOD nVtces;
vtx: NAT ← shape.surfaces[i][cVtx]; -- current vertex in shape
nVtx: NAT ← shape.surfaces[i][nextVtx]; -- at far end of edge
lVtx: NAT ← shape.surfaces[i][prevVtx]; -- previous vertex
FOR j:
NAT
IN [0..corners[vtx].length)
DO
IF corners[vtx][j].inVtx = lVtx
THEN {
-- is incoming edge from previous vertex?
jc: NAT ← j;
IF vtxCnt >= polyCorners[i].maxLength-2
THEN polyCorners[i] ← ExtendCornerSeq[polyCorners[i]];
polyCorners[i][vtxCnt] ← corners[vtx][jc]; -- copy corner
polyCorners[i][vtxCnt].inVtx ← prevVtx; -- change to polygon vertex numbers
polyCorners[i][vtxCnt].outVtx ← nextVtx;
polyCorners[i][vtxCnt].ptr ← cVtx; -- change to shape vertex number
vtxCnt ← vtxCnt + 1;
IF corners[vtx][j].outVtx # nVtx
THEN {
-- must be at a sliced corner
otherVtx: NAT ← corners[vtx][j].outVtx;
jc ← (j + corners[vtx].length-1) MOD corners[vtx].length;
FOR k:
NAT
IN [0..nVtces)
DO
IF otherVtx = shape.surfaces[i][k] THEN { otherVtx ← k; EXIT; };
ENDLOOP;
polyCorners[i][vtxCnt] ← corners[vtx][jc];
polyCorners[i][vtxCnt].inVtx ← polyCorners[i][vtxCnt-1].outVtx ← otherVtx;
polyCorners[i][vtxCnt].outVtx ← nextVtx;
polyCorners[i][vtxCnt].ptr ← cVtx;
vtxCnt ← vtxCnt + 1;
};
IF corners[vtx][jc].outVtx # nVtx
THEN SIGNAL G3dRender.Error[$MisMatch, "bad corner structure"];
EXIT;
};
ENDLOOP;
ENDLOOP;
polyCorners[i].length ← vtxCnt;
};
ENDLOOP;
renderData.props ← PutProp[renderData.props, $PatchCorners, polyCorners];
};
CheckDihedrals:
PROC[ shape: Shape, corners:
REF CornerSeqSeq ] ~ {
Find upper bound on dihedral angles at patch boundaries via midpoint analysis, adjust inner knot positions to zero angle where necessary
GetKnots:
PROC[rCrnr, lCrnr: Corner, pos: Triple]
RETURNS[left, mid, right: Triple] ~ {
mid ← Add[rCrnr.outDir, pos];
right ← Add[
IF rCrnr.double THEN rCrnr.interiorKnot2 ELSE rCrnr.interiorKnot,
pos
];
left ← Add[ lCrnr.interiorKnot, pos ];
};
FixKnots:
PROC[ corner:
REF CornerSeq, i:
NAT, scale:
REAL, clockWise:
BOOL ] ~ {
Clockwise refers to direction from vector out along edge to vector to interiorKnot
o:
NAT ←
IF clockWise
THEN (i + 1) MOD corner.length -- next edge (to right) in order around vtx
ELSE (i + corner.length-1) MOD corner.length; -- previous edge (to left) in order
knot: Triple ←
IF
NOT clockWise
OR
NOT corner[i].double
THEN corner[i].interiorKnot
ELSE corner[i].interiorKnot2;
midDir: Triple ← IF NOT clockWise THEN corner[i].inDir ELSE corner[i].outDir;
dist: Triple ← Sub3[ knot, midDir ];
IF
NOT ( corner[i].double
-- not double corner or open edge
OR (
NOT clockWise
AND corner[o].inVtx # corner[i].outVtx)
OR (clockWise
AND corner[o].outVtx # corner[i].inVtx) )
THEN {
-- Scale outDir of next edge to keep line connecting knots straight
nextKnot: Triple ←
IF
NOT clockWise
OR
NOT corner[o].double
THEN corner[o].interiorKnot
ELSE corner[o].interiorKnot2;
sideDir: Triple ← IF NOT clockWise THEN corner[o].inDir ELSE corner[o].outDir;
prtDist: Triple ← Sub3[ knot, sideDir ];
whlDist: Triple ← Sub3[ knot, nextKnot ];
ratio:
REAL ← Length[prtDist] / Length[whlDist];
Modulate effect of scale to keep knot -> sideDir -> nextKnot linear
sideDir ← G3dVector.Mul[ sideDir, scale + (1.0 - scale) * ratio ];
IF
NOT clockWise
THEN corner[i].outDir ← corner[o].inDir ← sideDir -- update matching directions
ELSE corner[i].inDir ← corner[o].outDir ← sideDir;
};
knot ← Add[ G3dVector.Mul[dist, scale], midDir ];
IF
NOT corner[i].double
-- store modified knot position
THEN corner[i].interiorKnot ← knot
ELSE IF corner[i].interiorKnot2 = corner[i].interiorKnot
THEN corner[i].interiorKnot2 ← corner[i].interiorKnot ← knot
ELSE
IF
NOT clockWise
THEN corner[i].interiorKnot ← knot
ELSE corner[i].interiorKnot2 ← knot;
};
FOR v:
NAT
IN [0..shape.vertices.length)
DO
IF corners[v] #
NIL
THEN {
-- check each vtx.
vtx: Vertex ← shape.vertices[v];
FOR i:
NAT
IN [0..corners[v].length)
DO
-- find inner knots for each outgoing edge
left, leftNear, leftFar, mid, midNear, midFar, right, rightNear, rightFar: Triple;
cosang: REAL;
oppIndx: NAT;
last: NAT ← (i + corners[v].length-1) MOD corners[v].length;
oppVtx: NAT ← corners[v][i].outVtx;
IF oppVtx # corners[v][last].inVtx THEN LOOP; -- skip if open edge
IF corners[v][i].ptr = oppVtx THEN LOOP; -- skip if touched from other end
[leftNear, midNear, rightNear] ← GetKnots[
-- get middle knots closest to this end
corners[v][i], corners[v][last], vtx.point
];
IF leftNear = midNear OR rightNear = midNear THEN LOOP; -- ignore creases
FOR j:
NAT
IN [0..corners[oppVtx].length)
DO
-- find other end of edge
IF corners[oppVtx][j].outVtx = v
THEN {
last: NAT ← (j + corners[oppVtx].length-1) MOD corners[oppVtx].length;
[rightFar, midFar, leftFar] ← GetKnots[
-- get knots at other end
corners[oppVtx][j], corners[oppVtx][last], vtx.point
];
corners[oppVtx][j].ptr ← v; corners[v][i].ptr ← oppVtx; -- tag edge as touched
oppIndx ← j;
EXIT;
};
ENDLOOP;
IF leftFar = midFar OR rightFar = midFar THEN LOOP; -- ignore creases
left ← G3dVector.Mul[ Add[leftNear, leftFar], 0.5 ];
mid ← G3dVector.Mul[ Add[midNear, midFar], 0.5 ];
right ← G3dVector.Mul[ Add[rightNear, rightFar], 0.5 ];
cosang ← Dot[ Normalize[ Sub3[mid, left] ], Normalize[ Sub3[right, mid] ] ];
IF cosang < .999
THEN {
-- cosine of dihedral angle shows its not zero
nearRatio:
REAL ←
-- ratio of edge lengths formed by far knots
Length[Sub3[rightNear, midNear]] / Length[Sub3[midNear, leftNear]];
farRatio:
REAL ←
-- ratio of edge lengths formed by near knots
Length[ Sub3[rightFar, midFar] ] / Length[ Sub3[midFar, leftFar] ];
targetRatio: REAL ← (nearRatio + farRatio)/ 2.0; -- try to adjust both to this ratio
IF Sub[nearRatio, farRatio] # 0.0
THEN
IF targetRatio > 1.0
-- not almost equal
THEN {
-- left side smaller
index: NAT ← (i + corners[v].length-1) MOD corners[v].length;
FixKnots[corners[v], index, nearRatio/targetRatio, FALSE]; -- near left knots
FixKnots[corners[oppVtx], oppIndx, farRatio/targetRatio, TRUE]; -- far left
}
ELSE {
-- right side smaller
oppIndx ← (oppIndx + corners[oppVtx].length-1) MOD corners[oppVtx].length;
FixKnots[corners[v], i, targetRatio/nearRatio, TRUE]; -- near right knots
FixKnots[corners[oppVtx], oppIndx, targetRatio/farRatio, FALSE]; -- far right
};
};
ENDLOOP;
};
ENDLOOP;
};
BuildInteriorKnots:
PROC[ corner:
REF CornerSeq ] ~ {
FOR i:
NAT
IN [0..corner.length)
DO
cosAng: REAL ← Dot[corner[i].outDir, corner[i].inDir]; -- dot product
cosAng ← cosAng / Length[corner[i].outDir]; -- normalize
cosAng ← cosAng / Length[corner[i].inDir]; -- and you get cosine
SELECT
TRUE
FROM
cosAng > 0.99 => {
-- same direction, set everything to the same point
corner[i].interiorKnot ← corner[i].inDir ← corner[i].outDir ← G3dVector.Mul[
Add[ corner[i].inDir, corner[i].outDir ], 0.5
];
corner[(i + corner.length-1) MOD corner.length].inDir ← corner[i].outDir; -- prev.
corner[(i + 1) MOD corner.length].outDir ← corner[i].inDir; -- next
IF corner[i].double THEN corner[i].interiorKnot2 ← corner[i].interiorKnot;
};
cosAng < -0.99 =>
IF corner[i].double
-- opposite directions
THEN {
j: NAT ← (i+1) MOD corner.length;
WHILE corner[j].inDir = corner[i].inDir
DO
-- search clockwise for another dir.
j ← (j+1) MOD corner.length; -- should go to right
ENDLOOP;
corner[i].interiorKnot ← Sub3[
-- subtract to get interior knots
corner[i].inDir, G3dVector.Mul[corner[j].inDir, 0.5] ];
corner[i].interiorKnot2 ← Sub3[
corner[i].outDir, G3dVector.Mul[corner[j].inDir, 0.5] ];
}
ELSE SIGNAL G3dRender.Error[$MisMatch, "corner should be double"];
ENDCASE =>
IF corner[i].double
-- other angles
THEN {
corner[i].interiorKnot2 ← corner[i].interiorKnot ←
Add[ corner[i].inDir, corner[i].outDir ];
corner[i].interiorKnot ← Add[
corner[i].inDir,
ScaleTangent[ -- scale to arc from inDir to outDir
corner[i].outDir,
Sub3[corner[i].outDir, corner[i].inDir]
]
];
corner[i].interiorKnot2 ← Add[
corner[i].outDir,
ScaleTangent[ -- scale to arc from outDir to inDir
corner[i].inDir,
Sub3[corner[i].inDir, corner[i].outDir]
]
];
}
ELSE corner[i].interiorKnot ← Add[ --
sum directions
corner[i].inDir, corner[i].outDir
];
ENDLOOP;
};
Procedures for computing tangent vectors at vertices
GetTangents: ShapeProc ~ {
Build endpoint tangents for each edge of a polygon
corners: REF CornerSeqSeq;
Pass through polygon structure building corner structure.
corners ← GetNormalsAndDirections[context, shape]; -- Get vertex normals, edge directions
Check for vertices with only three edges. If not open edges, split a polygon to make 4 edges
ForceFourCorners[corners, shape];
Order contiguous polygons around vertex
FOR i:
NAT
IN [0..corners.length)
DO
-- sort corners to clockwise order by matching edges
IF corners[i] # NIL THEN corners[i] ← SortCtlPoint[ corners[i] ];
ENDLOOP;
Build tangents at corners around each vertex. By projecting edge directions on plane given by normal
FOR i:
NAT
IN [0..corners.length)
DO
nCorners: NAT ← IF corners[i] # NIL THEN corners[i].length ELSE 0;
FOR this:
NAT
IN [0..nCorners)
DO
last: NAT ← (this + nCorners-1) MOD nCorners;
corners[i][this].outDir ← GetSlopeVec[ corners[i][this].normal, corners[i][this].outDir ];
IF corners[i][last].inVtx = corners[i][this].outVtx
-- matches previous corner
THEN corners[i][last].inDir ← corners[i][this].outDir -- copy vector
ELSE corners[i][last].inDir ← GetSlopeVec[
-- open edge, compute vector
corners[i][last].normal, corners[i][last].inDir
];
ENDLOOP;
ENDLOOP;
Make opposing pairs of tangents continuous. Always make open edges continuous. Reduce larger vertices to 4 directions by collapsing smaller angles
FOR i:
NAT
IN [0..corners.length)
DO
IF corners[i] # NIL THEN corners[i] ← FindContinuousEdges[ shape, i, corners[i] ];
ENDLOOP;
BuildBezierData[shape, corners]; -- convert patches to Bezier form
RETURN[shape];
};
GetNormalsAndDirections:
PROC[context: Context, shape: Shape]
RETURNS[
REF CornerSeqSeq] ~ {
Get vertex normals robustly ( using robust polygon normal )
Find incoming and outgoing directions for each polygon at a vertex
corners: REF CornerSeqSeq ← NEW[ CornerSeqSeq[shape.vertices.length] ];
angles: RealSequence ← NEW[RealSequenceRep[8]];
IF
NOT shape.vertices.valid.normal
THEN
FOR i:
NAT
IN [0..shape.vertices.length)
DO
IF shape.vertices[i] # NIL THEN shape.vertices[i].normal ← nullTriple; -- Clear vtx nmls
ENDLOOP;
FOR i:
NAT
IN [0..shape.surfaces.length)
DO
IF shape.surfaces[i] #
NIL
THEN {
nVtces: NAT ← shape.surfaces[i].length; -- do for all polys
smallest: NAT ← LAST[NAT]; -- smallest angle in triangle (default value harmless)
IF angles.maxLength < nVtces
THEN angles ←
NEW[RealSequenceRep[nVtces]];
Get normals robustly(?)
IF NOT shape.vertices.valid.normal THEN GetPolyNormals[shape, shape.surfaces[i]];
IF nVtces # 4
THEN {
smallestSize: REAL; -- Find smallestSize angle within non-quadrilateral
FOR cVtx:
NAT
IN [0..nVtces)
DO
vtx: NAT ← shape.surfaces[i][cVtx];
nVtx: NAT ← shape.surfaces[i][(cVtx + 1) MOD nVtces];
lVtx: NAT ← shape.surfaces[i][(cVtx + nVtces - 1) MOD nVtces];
angles[cVtx] ← GetAngle[ shape, vtx, lVtx, nVtx ];
IF angles[cVtx] < smallestSize
OR cVtx = 0
THEN { smallestSize ← angles[cVtx]; smallest ← cVtx; };
ENDLOOP;
};
Build corner structure
FOR cVtx:
NAT
IN [0..nVtces)
DO
-- get direction vectors for each edge at vtx.
vtx: NAT ← shape.surfaces[i][cVtx];
nVtx: NAT ← shape.surfaces[i][(cVtx + 1) MOD nVtces];
lVtx: NAT ← shape.surfaces[i][(cVtx + nVtces - 1) MOD nVtces];
corners[vtx] ← UpdateCornerVecSeq[
corners[vtx],
[ inVtx: lVtx, outVtx: nVtx,
-- store number of incoming vertex and outgoing vertex
ptr: i, -- store polygon number, in case needed
inDir: G3dVector.Sub[
shape.vertices[lVtx].point, shape.vertices[vtx].point ], -- dir. to incoming vertex
outDir: G3dVector.Sub[
shape.vertices[nVtx].point, shape.vertices[vtx].point ], -- outgoing direction
double: IF cVtx = smallest THEN TRUE ELSE FALSE -- doubled (degenerate edge)
]
];
ENDLOOP;
Add extra edges for big polygons
IF nVtces > 4 THEN SplitBigPoly[shape, i, corners, angles];
};
ENDLOOP;
corners.length ← shape.vertices.length;
FOR i:
NAT
IN [0..shape.vertices.length)
DO
-- normalize new vertex normals, store in corners
IF shape.vertices[i] #
NIL
THEN {
OPEN shape.vertices[i];
IF Length[ normal ] > shape.sphereExtent.radius * .0001
THEN normal ← Normalize[ normal ]
ELSE normal ← nullTriple; -- likely unused, set default to stop trouble
IF corners[i] #
NIL
THEN
FOR j:
NAT
IN [0..corners[i].length)
DO
corners[i][j].normal ← normal;
ENDLOOP;
};
ENDLOOP;
RETURN[ corners ];
};
GetAngle:
PROC[ shape: Shape, vtx, lVtx, nVtx:
NAT]
RETURNS[
REAL] ~ {
e1: Triple ← Normalize[G3dVector.Sub[shape.vertices[lVtx].point, shape.vertices[vtx].point]];
e2: Triple ←Normalize[G3dVector.Sub[shape.vertices[nVtx].point, shape.vertices[vtx].point]];
angle: REAL ← Length[ Cross[e1, e2] ]; -- sine
dot: REAL ← Dot[e1, e2]; -- cosine angle
IF dot < 0 THEN angle ← 1.0 + (1.0 - angle); -- angle 0-180 => 0.0-2.0
RETURN[angle];
};
SplitBigPoly:
PROC[ shape: Shape, polyNo:
NAT,
corners:
REF CornerSeqSeq, angles: RealSequence ] ~ {
Split up big polygon, add extra edges to corners
poly: REF Patch ← G3dRender.PatchesFrom[shape][polyNo];
nVtces: NAT ← poly.nVtces;
largest: REAL ← 0.0; vtx, lVtx, nVtx, oVtx, increment, remainingVtces: NAT;
FOR i:
NAT
IN [0..nVtces)
DO
-- find largest angle for split point
IF angles[i] > largest THEN { largest ← angles[i]; vtx ← i; };
ENDLOOP;
nVtx ← (vtx + 1) MOD nVtces;
lVtx ← (vtx + nVtces - 1) MOD nVtces;
increment ← IF nVtces > 5 THEN 2 ELSE 1;
oVtx ←
IF angles[nVtx] < angles[lVtx]
-- get smaller adjacent angle
THEN (nVtx + increment) MOD nVtces
ELSE (lVtx + nVtces - increment) MOD nVtces;
InsertEdge[shape, polyNo, corners, vtx, oVtx];
InsertEdge[shape, polyNo, corners, oVtx, vtx];
remainingVtces ← nVtces - increment;
WHILE remainingVtces > 4
DO
Need to complete this to handle polygons with more than 6 sides!!!!
remainingVtces ← remainingVtces - increment;
ENDLOOP;
poly.props ← PutProp[poly.props, $Split, $ItIs];
};
InsertEdge:
PROC[ shape: Shape, polyNo:
NAT,
corners:
REF CornerSeqSeq, cVtx, oVtx:
NAT ] ~ {
poly: NatSequence ← shape.surfaces[polyNo];
nVtces: NAT ← poly.length;
vtx: NAT ← poly[cVtx];
oppVtx: NAT ← poly[oVtx];
nVtx: NAT ← poly[(cVtx + 1) MOD nVtces];
lVtx: NAT ← poly[(cVtx + nVtces - 1) MOD nVtces];
FOR i:
NAT
IN [0..corners[vtx].length)
DO
IF corners[vtx][i].outVtx = nVtx
AND corners[vtx][i].inVtx = lVtx
THEN {
corners[vtx] ← UpdateCornerVecSeq[
-- add new vtx to end of sequence
corners[vtx],
[ inVtx: lVtx, outVtx: oppVtx, ptr: corners[vtx][i].ptr,
normal: corners[vtx][i].normal,
inDir: G3dVector.Sub[
-- dir to incoming Vtx
shape.vertices[lVtx].point, shape.vertices[vtx].point ],
outDir: G3dVector.Sub[
-- outgoing direction
shape.vertices[oppVtx].point, shape.vertices[vtx].point ]
]
];
corners[vtx][i].inVtx ← oppVtx; -- fix up vtx already in sequence
corners[vtx][i].inDir ← G3dVector.Sub[
shape.vertices[oppVtx].point, shape.vertices[vtx].point ];
EXIT;
};
ENDLOOP;
If triangle formed, mark corner opposite new edge as double
IF (cVtx + 2)
MOD nVtces = oVtx
THEN
FOR i:
NAT
IN [0..corners[nVtx].length)
DO
IF corners[nVtx][i].outVtx = oppVtx
AND corners[nVtx][i].inVtx = vtx
THEN { corners[nVtx][i].double ← TRUE; EXIT; };
ENDLOOP;
};
GetPolyNormals:
PROC[ shape: Shape, poly: NatSequence ] ~ {
Get polygon normal robustly ( allowing slightly concave polygons ). Sum of normals given at corners is assumed to be the dominant direction. Normals over 90 degrees off that are assumed to come from concave vertices and are therefore reversed.
normal: Triple ← nullTriple;
nVtces: NAT ← poly.length;
cNmls: TripleSequence ← NEW[TripleSequenceRep[nVtces]];
FOR cVtx:
NAT
IN [0..nVtces)
DO
-- get normal for each corner
vtx: NAT ← poly[cVtx];
nVtx: NAT ← poly[(cVtx + 1) MOD nVtces];
lVtx: NAT ← poly[(cVtx + nVtces - 1) MOD nVtces];
cNmls[cVtx] ← Cross[
-- in object space so do right-handed
G3dVector.Sub[ shape.vertices[lVtx].point, shape.vertices[vtx].point ],
G3dVector.Sub[ shape.vertices[nVtx].point, shape.vertices[vtx].point ]
];
IF unitizeNormals THEN cNmls[cVtx] ← Normalize[cNmls[cVtx]];
normal ← Add[ normal, cNmls[cVtx] ]; -- sum normals
ENDLOOP;
FOR cVtx:
NAT
IN [0..nVtces)
DO
-- Get normals robustly
IF Dot[ cNmls[cVtx], normal ] < 0.0
THEN {
cNmls[cVtx] ← Negate[ cNmls[cVtx] ];
normal ← Add[ normal, cNmls[cVtx] ]; -- cancel 1st entry
normal ← Add[ normal, cNmls[cVtx] ]; -- contribute to sum
};
ENDLOOP;
FOR cVtx:
NAT
IN [0..nVtces)
DO
-- Store robust vertex normals
vtx: NAT ← poly[cVtx];
IF shape.vertices[vtx] #
NIL
THEN
shape.vertices[vtx].normal ← Add[shape.vertices[vtx].normal, cNmls[cVtx]];
ENDLOOP;
};
UpdateCornerVecSeq:
PROC[corner:
REF CornerSeq, entry: Corner]
RETURNS[
REF CornerSeq] ~ {
newSeq: REF CornerSeq;
IF corner =
NIL
THEN newSeq ← NEW[ CornerSeq[6] ] -- get brand new sequence
ELSE
IF corner.length = corner.maxLength
THEN {
-- expand filled sequence
newSeq ← NEW[ CornerSeq[ corner.maxLength * 2 ] ];
FOR i:
NAT
IN [0..corner.maxLength)
DO
newSeq[i] ← corner[i]; -- copy into new sequence
ENDLOOP;
newSeq.length ← corner.length;
}
ELSE newSeq ← corner; -- no changes required
corner ← newSeq;
corner[corner.length] ← entry;
corner.length ← corner.length + 1;
RETURN[corner];
};
ForceFourCorners:
PROC[ corners:
REF CornerSeqSeq, shape: Shape ] ~ {
patch: PatchSequence ← G3dRender.PatchesFrom[shape];
FOR i:
NAT
IN [0..corners.length)
DO
IF corners[i] #
NIL
AND corners[i].length = 3
THEN {
ok: BOOLEAN ← FALSE;
FOR j:
NAT
IN [0..3)
DO
-- if a double edge included then all is ok
IF corners[i][j].double = TRUE THEN { ok ← TRUE; EXIT; };
ENDLOOP;
IF
NOT ok
THEN {
-- better split a polygon
cVtx, oppVtx: NAT ← LAST[NAT]; -- this vertex, opposing vertex to split to
smallestCorner, vertexNo, oppVtxNo, polyToSplit: NAT ← LAST[NAT];
FOR j:
NAT
IN [0..3)
DO
k: NAT ← corners[i][j].ptr; -- find a participating polygon
IF patch[k].nVtces > 3
AND GetProp[patch[k].props, $Split] =
NIL
THEN {
nVtces: NAT ← patch[k].nVtces; -- only triangles have doubled vertices
FOR v:
NAT
IN [0..nVtces)
DO
IF patch[k][v].vtxPtr = i
THEN {
cVtx ← v; oppVtx ← (v+2) MOD nVtces; -- get opposing vtx.
EXIT;
};
ENDLOOP;
IF corners[patch[k][oppVtx].vtxPtr].length = 3
-- find a 3-poly vertex
THEN {
Add to corners[surface[k][cVtx]] and corners[surface[k][oppVtx]]
InsertEdge[shape, k, corners, cVtx, oppVtx];
InsertEdge[shape, k, corners, oppVtx, cVtx];
patch[k].props ← PutProp[patch[k].props, $Split, $ItIs];
EXIT;
}
ELSE
IF corners[patch[k][oppVtx].vtxPtr].length < smallestCorner
THEN {
smallestCorner ← corners[patch[k][oppVtx].vtxPtr].length;
polyToSplit ← k; vertexNo ← cVtx; oppVtxNo ← oppVtx;
};
};
IF j = 2
THEN {
InsertEdge[shape, polyToSplit, corners, vertexNo, oppVtxNo];
InsertEdge[shape, polyToSplit, corners, oppVtxNo, vertexNo];
patch[polyToSplit].props ← Atom.PutPropOnList[
patch[polyToSplit].props, $Split, $ItIs
];
};
ENDLOOP;
};
};
ENDLOOP;
};
FindContinuousEdges:
PROC[ shape: Shape, vtx:
NAT, corner:
REF CornerSeq ]
RETURNS[
REF CornerSeq ] ~ {
All edges must be forced into 2 sets of opposing directions. If there are more than 4 edges, those forming the smallest angles will be collapsed
nCorners: NAT ← corner.length;
acrossFrom: REF NatSequenceSequence ← NEW[NatSequenceSequence[nCorners]];
FOR this:
NAT
IN [0..nCorners)
DO
acrossFrom[this] ← NEW[NatSequenceRep[nCorners]];
ENDLOOP;
Check for open edge, if there, align tangents unless included angle less than 45 degrees
IF corner[nCorners-1].inVtx # corner[0].outVtx
THEN {
-- open edge (should only be one)
cosAng:
REAL ← Dot[
Normalize[ corner[nCorners-1].inDir ],
Normalize[ corner[0].outDir ]
];
IF cosAng < minCosToAlignOpen
THEN {
-- included angle over limit (aligned => -1.0)
IF unitizeNormals
THEN {
-- normalize to give equal weight to direction
corner[nCorners-1].inDir ← Normalize[corner[nCorners-1].inDir];
corner[0].outDir ← Normalize[corner[0].outDir];
};
corner[nCorners-1].inDir ← Add[
-- sum to get aligned direction
corner[nCorners-1].inDir, G3dVector.Negate[corner[0].outDir]
];
corner[0].outDir ← G3dVector.Negate[corner[nCorners-1].inDir]; -- opposite dir
};
}
ELSE
SELECT nCorners
FROM
-- no open edge
1, 2 => SIGNAL G3dRender.Error[$MisMatch, "too few edges at vertex"];
3 =>
FOR i:
NAT
IN [0..3)
DO
-- find a doubled corner and set its angle to 180 degrees
IF corner[i].double
THEN {
corner[i].outDir ← Sub3[ corner[i].outDir, corner[i].inDir ];
corner[(i + 2) MOD 3].inDir ← corner[i].outDir;
corner[i].inDir ← G3dVector.Negate[corner[i].outDir];
corner[(i + 1) MOD 3].outDir ← corner[i].inDir;
EXIT;
};
IF i = 2 THEN SIGNAL G3dRender.Error[$MisMatch, "Three edges at vertex"];
ENDLOOP;
4 =>
FOR i:
NAT
IN [0..2)
DO
-- align opposing vertices if 4
o: NAT ← i+2; o1: NAT ← i+1; i1: NAT ← (i+3) MOD 4; -- opposite, next, and prev.
corner[o].outDir ← corner[o1].inDir ← Add[
-- sum for aligned dir
corner[o].outDir, G3dVector.Negate[corner[i].outDir]
];
corner[i].outDir ← corner[i1].inDir ← G3dVector.Negate[corner[o].outDir];
ENDLOOP;
IF nCorners > 4 THEN AlignBigCtlPoint[ corner, nCorners ];
FOR this:
NAT
IN [0..nCorners)
DO
-- go back over tangents and scale properly
last: NAT ← (this + nCorners -1) MOD nCorners;
corner[this].outDir ← ScaleTangent[
corner[this].outDir,
G3dVector.Sub[shape.vertices[corner[this].outVtx].point, shape.vertices[vtx].point]
];
IF corner[last].inVtx = corner[this].outVtx
THEN corner[last].inDir ← corner[this].outDir
ELSE corner[last].inDir ← ScaleTangent[
corner[last].inDir,
G3dVector.Sub[shape.vertices[corner[last].inVtx].point, shape.vertices[vtx].point]
];
ENDLOOP;
RETURN[ corner ];
};
AlignBigCtlPoint:
PROC[ corner:
REF CornerSeq, nCorners:
NAT ] ~ {
Collapse smallest angles until only 4 directions
sumDirections: NAT ← nCorners;
FOR i: NAT IN [0..nCorners) DO corner[i].ptr ← 0; ENDLOOP;
WHILE sumDirections > 4
DO
smallestVtx, next, last, start: NAT;
smallestAng: REAL ← 0.0; -- actually largest cosine of the angle
FOR i:
NAT
IN [0..nCorners)
DO
IF corner[i].ptr = 0 THEN { start ← i; EXIT; }; -- find non-collapsed angle
ENDLOOP;
FOR i:
NAT
IN [0..nCorners)
DO
-- get angle between outDir and following outDir
cosAng: REAL;
this: NAT ← (i + start) MOD nCorners;
next ← (this + 1) MOD nCorners;
cosAng ← Dot[ Normalize[ corner[next].outDir ], Normalize[ corner[this].outDir ] ];
IF cosAng > smallestAng
AND cosAng < 0.9999
THEN {
-- ignore collapsed angles
smallestAng ← cosAng; smallestVtx ← this; -- smallest angle (largest cosine
};
ENDLOOP;
corner[smallestVtx].ptr ← 1; -- tag first of pair forming smallest angle
last ← (smallestVtx + nCorners-1) MOD nCorners; -- step back past other tagged angles
WHILE corner[last].ptr # 0
DO last ← (last + nCorners-1)
MOD nCorners;
ENDLOOP;
Found start of sequence of collapsed angles
last ← (last + 1) MOD nCorners; -- first tagged corner of collapsed sequence
next ← last;
WHILE corner[next].ptr # 0
DO
-- now sum all the directions involved
next ← (next + 1) MOD nCorners;
corner[last].outDir ← Add[ corner[last].outDir, corner[next].outDir ];
ENDLOOP;
next ← last;
WHILE corner[next].ptr # 0
DO
-- now set all collapsed corners with direction
next ← (next + 1) MOD nCorners;
corner[next].outDir ← corner[last].outDir;
ENDLOOP;
sumDirections ← 0;
FOR i:
NAT
IN [0..nCorners)
DO
-- count unpaired and leading edges
IF corner[i].ptr = 0 THEN sumDirections ← sumDirections + 1;
ENDLOOP;
ENDLOOP;
Now, align four directions
IF corner[0].outVtx # corner[nCorners-1].inVtx
THEN {
-- open edge, everything aligned with open edge and one other dir.
i: NAT ← 0;
WHILE corner[i].ptr # 0
DO
-- align anything paired with first edge to open edge
corner[i].outDir ← G3dVector.Negate[ corner[nCorners-1].inDir ];
IF i > 0 THEN corner[i-1].inDir ← corner[i].outDir;
i ← i + 1;
ENDLOOP;
FOR j:
NAT
IN (i..nCorners)
DO
-- align everything else to single direction
corner[i].outDir ← Add[ corner[i].outDir, corner[j].outDir ];
ENDLOOP;
FOR j:
NAT
IN (i..nCorners)
DO
corner[j].outDir ← corner[i].outDir;
corner[j-1].inDir ← corner[j].outDir;
ENDLOOP;
}
ELSE {
-- no open edge, find 4 groups, align directions, reload directions
directions: ARRAY [0..4) OF Triple ← ALL[nullTriple];
weights: ARRAY [0..4) OF NAT ← ALL[0];
j, start:
NAT ← 0;
Find 4 directions
FOR i:
NAT
IN [0..nCorners)
DO
-- find non-collapsed corner to start with
IF corner[i].ptr = 0 THEN { start ← i; EXIT; };
ENDLOOP;
start ← (start + 1) MOD nCorners; -- guaranteed not paired with last corner
directions[0] ← corner[start].outDir; weights[0] ← 1; -- therefore 1st direction
FOR k:
NAT
IN [1..nCorners)
DO
i: NAT ← (k + start) MOD nCorners;
IF corner[(i + nCorners-1)
MOD nCorners].ptr = 0
-- not paired with last corner
THEN { j ← j + 1; directions[j] ← corner[i].outDir; weights[j] ← 1; }
ELSE weights[j] ← weights[j] + 1;
ENDLOOP;
directions[0] ← Sub3[
-- align 4 directions
G3dVector.Mul[ directions[0], weights[0] ],
G3dVector.Mul[ directions[2], weights[2] ]
];
directions[2] ← G3dVector.Negate[ directions[0] ];
directions[1] ← Sub3[
G3dVector.Mul[ directions[1], weights[1] ],
G3dVector.Mul[ directions[3], weights[3] ]
];
directions[3] ← G3dVector.Negate[ directions[1] ];
j ← 0;
corner[start].outDir ← directions[0];
corner[(start + nCorners-1) MOD nCorners].inDir ← corner[start].outDir;
FOR k:
NAT
IN [1..nCorners)
DO
-- reload directions
i: NAT ← (k + start) MOD nCorners;
IF corner[(i + nCorners-1) MOD nCorners].ptr = 0 THEN j ← j + 1;
corner[i].outDir ← directions[j];
corner[(i + nCorners-1) MOD nCorners].inDir ← corner[i].outDir;
ENDLOOP;
};
};
SortCtlPoint:
PROC[corner:
REF CornerSeq]
RETURNS[
REF CornerSeq] ~ {
Sort polygon entries to clockwise order at each vertex, ensure discontinuities are at extremes
Build chain of corners by checking both ends of chain against all remaining unattached corners, only one chain allowed, since only one open edge allowed at vertex
nCrnrs: NAT ← corner.length;
someLeft, someFound: BOOLEAN ← TRUE;
newSeq: REF CornerSeq ← NEW[CornerSeq[nCrnrs]];
newSeq[0] ← corner[0]; newSeq.length ← 1;
WHILE someLeft
DO
someLeft ← someFound ← FALSE;
FOR j:
NAT
IN [1..nCrnrs)
DO
IF newSeq[newSeq.length-1].inVtx = corner[j].outVtx
-- match last incoming edge
THEN {
-- next corner in clockwiser order
newSeq[newSeq.length] ← corner[j]; newSeq.length ← newSeq.length+1;
corner[j].outVtx ← corner[j].inVtx ← LAST[NAT]; -- no further use
someFound ← TRUE;
}
ELSE
IF newSeq[0].outVtx = corner[j].inVtx
-- match 1st outgoing edge
THEN {
-- previous corner in clockwiser order
FOR k:
NAT
DECREASING
IN [0..newSeq.length)
DO
newSeq[k+1] ← newSeq[k];
ENDLOOP;
newSeq[0] ← corner[j]; newSeq.length ← newSeq.length+1;
corner[j].outVtx ← corner[j].inVtx ← LAST[NAT]; -- no further use
someFound ← TRUE;
}
ELSE IF corner[j].outVtx # LAST[NAT] THEN someLeft ← TRUE; -- not done
ENDLOOP;
IF
NOT someFound
AND someLeft
THEN
-- more than one chain, apparently
SIGNAL G3dRender.Error[$Fatal, "Multiple open edges at a vertex not allowed"];
ENDLOOP;
IF newSeq.length > 0 THEN corner ← newSeq;
RETURN[ corner ];
};