ShapeTwiddleImpl.mesa
Last Edited by: Crow, April 8, 1988 1:38:51 pm PDT
DIRECTORY
Atom USING [ GetPropFromList, PropList, PutPropOnList ],
Real USING [ Fix, Float ],
Rope USING [ ROPE ],
CedarProcess USING [ DoWithPriority ],
G3dVector USING [ Cross, Sub, Length, Normalize ],
G3dMatrix USING [ Transform ],
ThreeDBasics USING [ Context, Error, NatSequence, PairSequence,
PtrPatch, PtrPatchSequence, Quad,
RGB, SetPosition, ShadingSequence, ShapeClass, ShapeInstance,
ShapeSequence, ShadingValue, Triple, TripleSequence, Vertex,
VertexInfo, VertexInfoProc, VertexInfoSequence, VertexSequence ],
SceneUtilities USING [ FindShape, NewShape ],
ShapeTwiddle USING [ NatPair ];
Types
LORA: TYPE ~ LIST OF REF ANY;
Context: TYPE ~ ThreeDBasics.Context;
RGB: TYPE ~ ThreeDBasics.RGB;
ShadingValue: TYPE ~ ThreeDBasics.ShadingValue;
Vertex: TYPE ~ ThreeDBasics.Vertex;
VertexSequence: TYPE ~ ThreeDBasics.VertexSequence;
VertexInfo: TYPE ~ ThreeDBasics.VertexInfo;
VertexInfoProc: TYPE ~ ThreeDBasics.VertexInfoProc;
VertexInfoSequence: TYPE ~ ThreeDBasics.VertexInfoSequence;
Triple: TYPE ~ ThreeDBasics.Triple;
TripleSequence: TYPE ~ ThreeDBasics.TripleSequence;
NatSequence: TYPE ~ ThreeDBasics.NatSequence;
PairSequence: TYPE ~ ThreeDBasics.PairSequence;
ShapeInstance: TYPE ~ ThreeDBasics.ShapeInstance;
PtrPatch: TYPE ~ ThreeDBasics.PtrPatch;
PtrPatchSequence: TYPE ~ ThreeDBasics.PtrPatchSequence;
ShadingSequence: TYPE ~ ThreeDBasics.ShadingSequence;
ShapeClass: TYPE ~ ThreeDBasics.ShapeClass;
NatPair: TYPE ~ ShapeTwiddle.NatPair; -- RECORD [x, y: NAT];
Shape Manipulations
ScaleShape:
PUBLIC
PROC [context:
REF Context, name: Rope.
ROPE, scale:
REAL,
xRatio, yRatio, zRatio:
REAL ← 1.0, applyXfm:
BOOLEAN ←
FALSE] ~ {
shape: REF ShapeInstance ← SceneUtilities.FindShape[ context, name ];
IF shape.positionInValid THEN ThreeDBasics.SetPosition[shape]; -- set position matrix
FOR i:
NAT
IN [0..shape.vertex.length)
DO
OPEN shape.vertex[i];
tx, ty, tz: REAL;
IF applyXfm
THEN [ [tx, ty, tz] ] ← G3dMatrix.Transform[ [x, y, z], shape.position]
ELSE { tx ← x; ty ← y; tz ← z; };
x ← tx * scale * xRatio;
y ← ty * scale * yRatio;
z ← tz * scale * zRatio;
ENDLOOP;
shape.boundingRadius ← shape.boundingRadius * scale * MAX[xRatio, yRatio, zRatio];
shape.shadingProps ← PutProp[
shape.shadingProps, $Scale,
NEW[ ThreeDBasics.Quad ← [scale, xRatio, yRatio, zRatio] ]
];
};
ScaleTexture:
PUBLIC
PROC [context:
REF Context, name: Rope.
ROPE, scale:
REAL,
xRatio, yRatio, zRatio:
REAL ← 1.0] ~ {
shape: REF ShapeInstance ← SceneUtilities.FindShape[ context, name ];
auxData: REF ← GetProp[ shape.shadingProps, $AuxiliaryVtxData ];
WITH auxData
SELECT
FROM
pairs:
REF PairSequence =>
FOR i:
NAT
IN [0..pairs.length)
DO
pairs[i].x ← pairs[i].x * scale * xRatio; pairs[i].y ← pairs[i].y * scale * yRatio;
ENDLOOP;
triples:
REF TripleSequence =>
FOR i:
NAT
IN [0..triples.length)
DO
triples[i].x ← triples[i].x * scale * xRatio; triples[i].y ← triples[i].y * scale * yRatio;
triples[i].z ← triples[i].z * scale * zRatio;
ENDLOOP;
ENDCASE => SIGNAL ThreeDBasics.Error[[$Unimplemented, "Unrecognized coord type"]];
shape.shadingProps ← PutProp[
shape.shadingProps, $TextureScale,
NEW[ ThreeDBasics.Quad ← [scale, xRatio, yRatio, zRatio] ]
];
};
SortPair: TYPE ~ RECORD [vtx, next: NAT];
SortSequence: TYPE ~ RECORD[SEQUENCE length: NAT OF REF SortPair];
CleanUp:
PUBLIC PROC [context:
REF Context, name: Rope.
ROPE, deSeam:
BOOLEAN ←
FALSE,
tolerance:
REAL ← 0.0] ~ {
delete excess vertices, join identical ones, etc.
currPos: NAT ← 0;
shape: REF ShapeInstance ← SceneUtilities.FindShape[ context, name ];
surface: REF PtrPatchSequence ← NARROW[shape.surface];
table: REF NatSequence ← NEW[ NatSequence[shape.vertex.length] ];
buckets: REF SortSequence ← NEW[SortSequence[5 * shape.vertex.length / 4]];
nextBucket: NAT ← (shape.vertex.length / 4) + 1;
newVtx: REF VertexSequence;
newShade: REF ShadingSequence;
Action:
PROC ~ {
IF deSeam
THEN {
minX, maxX, scale: REAL;
[minX, maxX] ← Bounds[context, name];
scale ← (shape.vertex.length / 4) / (maxX - minX);
IF 1.0 / scale < tolerance
THEN SIGNAL ThreeDBasics.Error[[$Mismatch, "Tolerance too large"]];
FOR i:
NAT
IN [0..shape.vertex.length)
DO
-- bucket sort vertices
index: NAT ← Real.Fix[ (shape.vertex[i].x - minX) * scale ];
IF buckets[index] #
NIL
THEN {
buckets[nextBucket] ← NEW[SortPair];
buckets[nextBucket].next ← buckets[index].next; -- put on next-to-head of list
buckets[index].next ← nextBucket; -- reset first pointer
index ← nextBucket; nextBucket ← nextBucket + 1;
}
ELSE {
buckets[index] ← NEW[SortPair]; -- bucket hit for first time
buckets[index].next ← 0;
};
buckets[index].vtx ← i; -- store vertex pointer
ENDLOOP;
FOR i:
NAT
IN [1..table.length)
DO
-- Coalesce nearby vertices
vtx: REF Vertex ← shape.vertex[i];
xBucket:
NAT ←
MAX[
1,
MIN[shape.vertex.length-1, INTEGER[ Real.Fix[ (vtx.x - minX)*scale] ]]
];
table[i] ← i; -- set to identity value
FOR j:
NAT
IN [xBucket-1 .. xBucket+1]
DO
-- search this and last and next buckets
index: NAT ← j;
WHILE buckets[index] #
NIL DO
k: NAT ← buckets[index].vtx;
diff:
REAL ← G3dVector.Length[ G3dVector.Sub[
-- check distance
[vtx.x, vtx.y, vtx.z],
[shape.vertex[k].x, shape.vertex[k].y, shape.vertex[k].z]
] ];
IF diff <= tolerance THEN IF k < table[i] THEN table[i] ← k; -- reset if smaller
index ← buckets[index].next; IF index = 0 THEN EXIT;
ENDLOOP;
ENDLOOP;
ENDLOOP;
FOR i:
NAT
IN [0..shape.numSurfaces)
DO
-- retarget vertex pointers
IF surface[i] #
NIL
THEN
FOR j:
NAT
IN [0..surface[i].nVtces)
DO
surface[i].vtxPtr[j] ← table[surface[i].vtxPtr[j]];
ENDLOOP;
ENDLOOP;
IF shape.class.type = $ConvexPolygon
THEN {
FOR i:
NAT
IN [0..shape.numSurfaces)
DO
-- eliminate duplicated polygon vertices
vtx: NAT ← 0;
IF surface[i] #
NIL
THEN
FOR j:
NAT
IN [0..surface[i].nVtces)
DO
k: NAT ← (j-1 + surface[i].nVtces) MOD surface[i].nVtces;
IF surface[i].vtxPtr[j] # surface[i].vtxPtr[k]
THEN {
surface[i].vtxPtr[vtx] ← surface[i].vtxPtr[j];
vtx ← vtx + 1;
};
ENDLOOP;
surface[i].nVtces ← vtx;
ENDLOOP;
};
}; -- end deSeaming block
FOR i: NAT IN [0..table.length) DO table[i] ← 0; ENDLOOP;
FOR i:
NAT
IN [0..shape.numSurfaces)
DO
-- build vertex reference count
IF surface[i] #
NIL
THEN
FOR j:
NAT
IN [0..surface[i].nVtces)
DO
table[surface[i].vtxPtr[j]] ← table[surface[i].vtxPtr[j]] + 1;
ENDLOOP;
ENDLOOP;
currPos ← 0;
FOR i:
NAT
IN [0..table.length)
DO
-- collapse vertex array and keep audit trail
IF table[i] # 0
THEN {
shape.vertex[currPos] ← shape.vertex[i];
shape.shade[currPos] ← shape.shade[i];
table[i] ← currPos;
currPos ← currPos + 1;
};
ENDLOOP;
newVtx ← NEW[ VertexSequence[currPos] ]; newVtx.length ← currPos;
newShade ← NEW[ ShadingSequence[currPos] ]; newShade.length ← currPos;
FOR i:
NAT
IN [0..currPos)
DO
-- copy into new sequences of proper length
newVtx[i] ← shape.vertex[i];
newShade[i] ← shape.shade[i];
ENDLOOP;
shape.vertex ← newVtx;
shape.shade ← newShade;
FOR i:
NAT
IN [0..shape.numSurfaces)
DO
-- retarget vertex pointers
FOR j:
NAT
IN [0..surface[i].nVtces)
DO
surface[i].vtxPtr[j] ← table[surface[i].vtxPtr[j]];
ENDLOOP;
ENDLOOP;
};
CedarProcess.DoWithPriority[background, Action];
};
CopyShape:
PUBLIC PROC [context:
REF Context, dstName, srcName: Rope.
ROPE]
RETURNS[
REF ShapeInstance] ~ {
dstShape: REF ShapeInstance ← SceneUtilities.NewShape[dstName];
srcShape: REF ShapeInstance ← SceneUtilities.FindShape[ context, srcName ];
srcSurface: REF PtrPatchSequence ← NARROW[srcShape.surface];
dstSurface: REF PtrPatchSequence;
currPos: NAT ← 0;
shape: REF ShapeInstance ← SceneUtilities.NewShape[dstName];
dstShape.orientation ← srcShape.orientation;
dstShape.location ← srcShape.location;
dstShape.rotation ← srcShape.rotation;
dstShape.axisBase ← srcShape.axisBase;
dstShape.axisEnd ← srcShape.axisEnd;
dstShape.centroid ← srcShape.centroid;
dstShape.boundingRadius ← srcShape.boundingRadius;
dstShape.vertex ← NEW[ThreeDBasics.VertexSequence[srcShape.vertex.length] ];
dstShape.vertex.length ← srcShape.vertex.length;
FOR i:
NAT
IN [0..srcShape.vertex.length)
DO
dstShape.vertex[i] ← srcShape.vertex[i];
ENDLOOP;
dstShape.shade ← NEW[ ShadingSequence[srcShape.shade.length] ];
dstShape.shade.length ← srcShape.shade.length;
FOR i:
NAT
IN [0..srcShape.shade.length)
DO
dstShape.shade[i] ← srcShape.shade[i];
ENDLOOP;
dstShape.surface ← NEW[ PtrPatchSequence[srcShape.numSurfaces] ];
dstSurface ← NARROW[dstShape.surface, REF PtrPatchSequence];
FOR i:
NAT
IN [0..srcShape.numSurfaces)
DO
dstSurface[i] ← srcSurface[i];
ENDLOOP;
dstShape.numSurfaces ← srcShape.numSurfaces;
dstShape.shadingProps ← srcShape.shadingProps;
dstShape.props ← srcShape.props;
RETURN[dstShape];
};
Combine:
PUBLIC PROC [context:
REF Context, dstName, src1, src2: Rope.
ROPE]
RETURNS[
REF ShapeInstance] ~ {
shape: REF ShapeInstance ← SceneUtilities.NewShape[dstName];
shape1: REF ShapeInstance ← SceneUtilities.FindShape[ context, src1 ];
shape2: REF ShapeInstance ← SceneUtilities.FindShape[ context, src2 ];
surface1: REF PtrPatchSequence ← NARROW[shape1.surface];
surface2: REF PtrPatchSequence ← NARROW[shape2.surface];
surface: REF PtrPatchSequence;
shape.vertex ← NEW[ -- copy vertices
ThreeDBasics.VertexSequence[shape1.vertex.length + shape2.vertex.length] ];
shape.vertex.length ← shape.vertex.maxLength;
FOR i:
NAT
IN [0..shape1.vertex.length)
DO
shape.vertex[i] ← shape1.vertex[i];
[[shape.vertex[i].x, shape.vertex[i].y, shape.vertex[i].z]] ← G3dMatrix.Transform[
[shape.vertex[i].x, shape.vertex[i].y, shape.vertex[i].z],
shape1.position
];
ENDLOOP;
FOR i:
NAT
IN [0..shape2.vertex.length)
DO
shape.vertex[i+shape1.vertex.length] ← shape2.vertex[i];
[[shape.vertex[i].x, shape.vertex[i].y, shape.vertex[i].z]] ← G3dMatrix.Transform[
[shape.vertex[i].x, shape.vertex[i].y, shape.vertex[i].z],
shape2.position
];
ENDLOOP;
shape.shade ← NEW[ -- copy shading values
ShadingSequence[shape1.shade.length + shape2.shade.length] ];
shape.shade.length ← shape.shade.maxLength;
FOR i:
NAT
IN [0..shape1.shade.length)
DO
shape.shade[i] ← shape1.shade[i];
ENDLOOP;
FOR i:
NAT
IN [0..shape2.shade.length)
DO
shape.shade[i+shape1.shade.length] ← shape2.shade[i];
ENDLOOP;
shape.numSurfaces ← shape1.numSurfaces + shape2.numSurfaces;
shape.surface ← NEW[ -- copy surfaces
PtrPatchSequence[shape1.numSurfaces + shape2.numSurfaces] ];
surface ← NARROW[shape.surface, REF PtrPatchSequence];
FOR i:
NAT
IN [0..shape1.numSurfaces)
DO
surface[i] ← surface1[i];
ENDLOOP;
FOR i:
NAT
IN [0..shape2.numSurfaces)
DO
base: NAT ← shape1.numSurfaces;
surface[i+base] ← surface2[i];
FOR j:
NAT
IN [0..surface[i+base].nVtces)
DO
-- redirect vertex pointers
surface[i+base].vtxPtr[j] ← surface[i+base].vtxPtr[j] + shape1.vertex.length
ENDLOOP;
ENDLOOP;
shape.shadingProps ← shape1.shadingProps;
shape.props ← shape1.props;
RETURN[shape];
};
DeletePatches:
PUBLIC PROC [context:
REF Context, dstName, srcName: Rope.
ROPE,
patchList:
LIST
OF NatPair]
RETURNS[
REF ShapeInstance] ~ {
currPos: NAT ← 0;
oldShape: REF ShapeInstance ← SceneUtilities.FindShape[ context, srcName ];
shape: REF ShapeInstance ← CopyShape[context, dstName, srcName];
surface: REF PtrPatchSequence;
surface ← NARROW[shape.surface, REF PtrPatchSequence];
FOR list:
LIST
OF NatPair ← patchList, list.rest
UNTIL list =
NIL
DO
FOR i:
NAT
IN [list.first.x..list.first.y]
DO
surface[i] ← NIL;
ENDLOOP;
ENDLOOP;
FOR i:
NAT
IN [0..shape.numSurfaces)
DO
-- collapse array
IF surface[i] #
NIL
THEN {
surface[currPos] ← surface[i];
currPos ← currPos + 1;
};
ENDLOOP;
shape.numSurfaces ← currPos;
RETURN[ shape ];
};
Bounds:
PUBLIC PROC [context:
REF Context, name: Rope.
ROPE]
RETURNS[xMin, xMax, yMin, yMax, zMin, zMax:
REAL] ~ {
shape: REF ShapeInstance ← SceneUtilities.FindShape[ context, name ];
xMin ← xMax ← shape.vertex[0].x;
yMin ← yMax ← shape.vertex[0].y;
zMin ← zMax ← shape.vertex[0].z;
FOR i:
NAT
IN (0..shape.vertex.length)
DO
-- get min and max in x, y, and z
IF shape.vertex[i].x < xMin
THEN xMin ← shape.vertex[i].x
ELSE IF shape.vertex[i].x > xMax THEN xMax ← shape.vertex[i].x;
IF shape.vertex[i].y < yMin
THEN yMin ← shape.vertex[i].y
ELSE IF shape.vertex[i].y > yMax THEN yMax ← shape.vertex[i].y;
IF shape.vertex[i].z < zMin
THEN zMin ← shape.vertex[i].z
ELSE IF shape.vertex[i].z > zMax THEN zMax ← shape.vertex[i].z;
ENDLOOP;
};
Procedures for expansion of/to polygons
ShapeDo:
PROC[ context:
REF Context, shape:
REF ShapeInstance, fullExpand:
BOOLEAN,
limitType:
ATOM, limit:
REAL]
RETURNS [
REF ShapeInstance] ~ {
MakeRoom:
PROC [] ~ {
-- ensure enough space for storing expanded shape
IF vertex =
NIL
-- first we attempt to guess at how much space will be needed
THEN vertex ← NEW[ VertexSequence[newPts.length * shape.numSurfaces] ]
ELSE
IF vertex.maxLength < newPts.length + ptIndex
-- then we expand as needed
THEN {
vertex2: REF VertexSequence;
IF vertex.length * 2 >
LAST[
CARDINAL]
THEN SIGNAL ThreeDBasics.Error[[$Unimplemented,
"Sequence too long (Dragon needed)"]];
vertex2 ← NEW[ VertexSequence[vertex.length*2] ];
FOR i:
NAT
IN [0..vertex.length)
DO
-- copy old sequence
IF vertex[i] #
NIL
THEN vertex2[i] ← NEW[ Vertex ← vertex[i]^ ]
ELSE vertex2[i] ← NEW[ Vertex ];
ENDLOOP;
vertex ← vertex2;
};
vertex.length ← vertex.maxLength;
IF shade =
NIL
-- first we attempt to guess at how much space will be needed
THEN shade ← NEW[ ShadingSequence[newPts.length * shape.numSurfaces] ]
ELSE
IF shade.length < newPts.length + ptIndex
-- then we expand as needed
THEN {
shade2: REF ShadingSequence ← NEW[ ShadingSequence[vertex.length*2] ];
FOR i:
NAT
IN [0..shade.length)
DO
-- copy old sequence
IF shade[i] #
NIL
THEN shade2[i] ← NEW[ ShadingValue ← shade[i]^ ]
ELSE shade2[i] ← NEW[ ShadingValue ];
ENDLOOP;
shade ← shade2;
};
shade.length ← shade.maxLength;
IF surface =
NIL
-- first we attempt to guess at how much space will be needed
THEN surface ← NEW[ PtrPatchSequence[newPatches.length * shape.numSurfaces] ]
ELSE
IF surface.length < newPatches.length + patchIndex
-- then we expand as needed
THEN {
surface2: REF PtrPatchSequence;
IF surface.length * 2 >
LAST[
NAT]
THEN SIGNAL ThreeDBasics.Error[[$Unimplemented,
"Sequence too long (Dragon needed)"]];
surface2 ← NEW[ PtrPatchSequence[surface.length*2] ];
FOR i:
NAT
IN [0..surface.length)
DO
-- copy old sequence
IF surface[i] #
NIL
THEN surface2[i] ← NEW[ PtrPatch ← surface[i]^ ]
ELSE surface2[i] ← NEW[ PtrPatch ];
ENDLOOP;
surface ← surface2;
};
surface.length ← surface.maxLength;
};
expand: PROC[shape: REF ShapeInstance, patch: REF PtrPatch, nPrSide: NAT]
RETURNS [REF VertexInfoSequence, REF PtrPatchSequence];
subdivide: PROC [shape: REF ThreeDBasics.ShapeInstance, patch: REF PtrPatch]
RETURNS [REF VertexInfoSequence, REF PtrPatchSequence];
patch: REF PtrPatchSequence ← NARROW[ shape.surface ];
vertex: REF ThreeDBasics.VertexSequence;
shade: REF ShadingSequence;
surface: REF PtrPatchSequence;
patchInfo: REF ShadingSequence ← shape.shadingClass.patchShade;
newPts: REF VertexInfoSequence;
newPatches: REF PtrPatchSequence;
ptIndex, patchIndex: INT ← 0;
SELECT shape.class.type
FROM
$Bezier => {
expand ← BezierParametricExpand;
subdivide ← BezierSubdivideExpand;
};
ENDCASE => SIGNAL ThreeDBasics.Error[[$Unimplemented, "Unknown surface type"]];
FOR pNum:
NAT
IN [0..shape.numSurfaces)
DO
IF fullExpand
-- expand patch
THEN [newPts, newPatches] ← expand[ shape, patch[pNum], Real.Fix[limit] ]
ELSE [newPts, newPatches] ← subdivide[ shape, patch[pNum] ];
MakeRoom[]; -- get storage space for expanded shape
FOR i:
NAT
IN [0..newPts.length)
DO
-- copy the vertices into the whole
vertex[i+ptIndex] ← NEW[ Vertex ];
vertex[i+ptIndex]^ ← newPts[i].coord;
shade[i+ptIndex] ← NEW[ ThreeDBasics.ShadingValue ];
shade[i+ptIndex]^ ← newPts[i].shade;
IF patchInfo #
NIL
THEN {
shade[i+ptIndex].r ← shade[i+ptIndex].r * patchInfo[pNum].r;
shade[i+ptIndex].g ← shade[i+ptIndex].g * patchInfo[pNum].g;
shade[i+ptIndex].b ← shade[i+ptIndex].b * patchInfo[pNum].b;
};
ENDLOOP;
FOR i:
NAT
IN [0..newPatches.length)
DO
-- copy the polygons into the whole
surface[i+patchIndex] ← NEW[ PtrPatch ];
surface[i+patchIndex].vtxPtr ← NEW[ NatSequence[newPatches[i].nVtces] ];
FOR j:
NAT
IN [0..newPatches[i].nVtces)
DO
surface[i+patchIndex].vtxPtr[j] ← newPatches[i].vtxPtr[j] + ptIndex;
ENDLOOP;
surface[i+patchIndex].type ← newPatches[i].type;
surface[i+patchIndex].oneSided ← newPatches[i].oneSided;
surface[i+patchIndex].dir ← newPatches[i].dir;
surface[i+patchIndex].nVtces ← newPatches[i].nVtces;
surface[i+patchIndex].clipState ← newPatches[i].clipState;
surface[i+patchIndex].props ← newPatches[i].props;
ENDLOOP;
ptIndex ← ptIndex + newPts.length; -- update the indices
patchIndex ← patchIndex + newPatches.length;
ENDLOOP;
IF fullExpand THEN shape.class.type ← $ConvexPolygon; -- set type to polygons if fully expanded
shape.vertex ← vertex; -- point the shape at the new data
shape.shade ← shade;
shape.surface ← surface;
shape.numSurfaces ← surface.length;
shape.shadingClass.patchShade ← NIL;
shape.shadingInValid ← TRUE;
shape.vtcesInValid ← TRUE;
RETURN[shape];
};
ShapeExpand:
PUBLIC
PROC[ context:
REF Context, name: Rope.
ROPE,
limitType:
ATOM ←
NIL, limit:
REAL ← 0.0]
RETURNS [
REF ShapeInstance] ~ {
Expands a whole shape, calling procedures supplied by the surface type
shape: REF ShapeInstance ← SceneUtilities.FindShape[ context, name ];
RETURN[ ShapeDo[ context, shape, TRUE, limitType, limit ] ];
};
ShapeSubdivide:
PUBLIC
PROC[ context:
REF Context, name: Rope.
ROPE,
limitType:
ATOM ←
NIL, limit:
REAL ← 0.0]
RETURNS [
REF ShapeInstance] ~ {
Subdivide a whole shape once, calling procedures supplied by the surface type
shape: REF ShapeInstance ← SceneUtilities.FindShape[ context, name ];
RETURN[ ShapeDo[ context, shape, FALSE, limitType, limit ] ];
};
BezierPtrPatchNormals:
PROC[ shape:
REF ShapeInstance, patch:
REF PtrPatch] ~ {
Get normals at control points, given by cross product of vectors formed from adjacent control points (limited to patch bounds, of course)
GetXProd:
PROC[vertex:
REF ThreeDBasics.VertexSequence, v1b, v1e, v2b, v2e:
NAT]
RETURNS[Triple] ~ {
RETURN [ G3dVector.Normalize[ G3dVector.Cross[
-- in object space so do right-handed
DiffPosns[ vertex[v1e]^, vertex[v1b]^ ],
DiffPosns[ vertex[v2e]^, vertex[v2b]^ ]
] ] ];
};
vertex: REF ThreeDBasics.VertexSequence ← shape.vertex;
shade: REF ThreeDBasics.ShadingSequence ← shape.shade;
FOR i:
INTEGER
IN [0..4)
DO
FOR j:
INTEGER
IN [0..4)
DO
k: NAT ← patch.vtxPtr[j + i*4];
IF shade[k].xn = 0.0
AND shade[k].yn = 0.0
AND shade[k].zn = 0.0
THEN {
-- untouched
v1Beg: NAT ← 4*i + MAX[j-1, 0]; v1End: NAT ← 4*i + MIN[j+1, 3];
v2Beg: NAT ← 4*MAX[i-1, 0] + j; v2End: NAT ← 4*MIN[i+1, 3] + j;
IF patch.vtxPtr[v1Beg] = patch.vtxPtr[v1End]
THEN {
-- try to fix coalesced points
v1Beg ← 4*MAX[i-1, 0] + MAX[j-1, 0];
v1End ← 4*MIN[i+1, 3] + MIN[j+1, 3];
IF patch.vtxPtr[v1Beg] = patch.vtxPtr[v1End]
THEN SIGNAL ThreeDBasics.Error[[$MisMatch, "DegeneratePatch"]];
};
IF patch.vtxPtr[v2Beg] = patch.vtxPtr[v2End]
THEN {
-- try to fix coalesced points
v2Beg ← 4*MAX[i-1, 0] + MAX[j-1, 0];
v2End ← 4*MIN[i+1, 3] + MIN[j+1, 3];
IF patch.vtxPtr[v2Beg] = patch.vtxPtr[v2End]
THEN SIGNAL ThreeDBasics.Error[[$MisMatch, "DegeneratePatch"]];
};
[[ shade[k].xn, shade[k].yn, shade[k].zn ]] ← GetXProd[ vertex,
patch.vtxPtr[v1Beg], patch.vtxPtr[v1End], patch.vtxPtr[v2Beg], patch.vtxPtr[v2End]
];
};
ENDLOOP;
ENDLOOP;
};
ApplyCubicBasis:
PROC[ v0, v1, v2, v3:
REF VertexInfo, f0, f1, f2, f3:
REAL ]
RETURNS[vOut:
REF VertexInfo] ~ {
shape: REF ShapeInstance ← NARROW[ Atom.GetPropFromList[v0.props, $Shape] ];
lerpProc: VertexInfoProc ← IF shape # NIL THEN shape.shadingClass.lerpVtxAux ELSE NIL;
vOut ← NEW[VertexInfo];
vOut.coord.x ← f0*v0.coord.x + f1*v1.coord.x + f2*v2.coord.x + f3*v3.coord.x;
vOut.coord.y ← f0*v0.coord.y + f1*v1.coord.y + f2*v2.coord.y + f3*v3.coord.y;
vOut.coord.z ← f0*v0.coord.z + f1*v1.coord.z + f2*v2.coord.z + f3*v3.coord.z;
vOut.shade.xn ← f0*v0.shade.xn + f1*v1.shade.xn + f2*v2.shade.xn + f3*v3.shade.xn;
vOut.shade.yn ← f0*v0.shade.yn + f1*v1.shade.yn + f2*v2.shade.yn + f3*v3.shade.yn;
vOut.shade.zn ← f0*v0.shade.zn + f1*v1.shade.zn + f2*v2.shade.zn + f3*v3.shade.zn;
vOut.shade.r ← f0*v0.shade.r + f1*v1.shade.r + f2*v2.shade.r + f3*v3.shade.r;
vOut.shade.g ← f0*v0.shade.g + f1*v1.shade.g + f2*v2.shade.g + f3*v3.shade.g;
vOut.shade.b ← f0*v0.shade.b + f1*v1.shade.b + f2*v2.shade.b + f3*v3.shade.b;
IF lerpProc #
NIL
THEN {
-- get auxiliary info from supplied proc
data: LORA ← LIST[v0.aux, vOut.aux, NEW[REAL ← f0], NEW[REAL ← 0.0]];
vOut.aux ← NIL; vOut^ ← lerpProc[ NIL, vOut^, data];
data ← LIST[ v1.aux, vOut.aux, NEW[REAL ← f1], NEW[REAL ← 1.0]];
vOut.aux ← NIL; vOut^ ← lerpProc[ NIL, vOut^, data];
data ← LIST[ v2.aux, vOut.aux, NEW[REAL ← f2], NEW[REAL ← 1.0]];
vOut.aux ← NIL; vOut^ ← lerpProc[ NIL, vOut^, data];
data ← LIST[ v3.aux, vOut.aux, NEW[REAL ← f3], NEW[REAL ← 1.0]];
vOut.aux ← NIL; vOut^ ← lerpProc[ NIL, vOut^, data];
}
ELSE vOut.aux ← v0.aux;
};
BezierParametricExpand:
PROC[shape:
REF ShapeInstance, patch:
REF PtrPatch, nPrSide:
NAT]
RETURNS [
REF VertexInfoSequence,
REF PtrPatchSequence] ~ {
vertex: REF ThreeDBasics.VertexSequence ← shape.vertex;
shade: REF ThreeDBasics.ShadingSequence ← shape.shade;
RowEval:
PROC[ v0, v1, v2, v3:
REF VertexInfo, numPts:
NAT ]
RETURNS [pt:
REF VertexInfoSequence] ~ {
pt ← NEW[ VertexInfoSequence[numPts] ]; pt.length ← numPts;
FOR i:
NAT
IN [0..numPts)
DO
t: REAL ← Real.Float[i] / (numPts-1); t2: REAL ← t * t; t3: REAL ← t2 * t;
f0: REAL ← -1.0*t3 + 3.0*t2 - 3.0*t + 1;
f1: REAL ← 3.0*t3 - 6.0*t2 + 3.0*t;
f2: REAL ← -3.0*t3 + 3.0*t2;
f3: REAL ← 1.0*t3;
pt[i] ← ApplyCubicBasis[v0, v1, v2, v3, f0, f1, f2, f3];
ENDLOOP;
};
row: ARRAY [0..4) OF REF VertexInfoSequence;
colA, colB: REF VertexInfoSequence;
vtxCnt, ptchCnt: NAT ← 0;
nVtces: NAT ← (nPrSide+1) * (nPrSide+1);
outVtx: REF VertexInfoSequence ← NEW[ VertexInfoSequence[nVtces] ];
outPatch: REF PtrPatchSequence ← NEW[ PtrPatchSequence[nPrSide*nPrSide] ];
ctlPtRow:
ARRAY [0..4)
OF
REF VertexInfo;
Get special output type for weird things like displacement mapping
outputType: ATOM ← NARROW[ Atom.GetPropFromList[ patch.props, $InterimPatchType ] ];
IF outputType =
NIL
THEN outputType ← $ConvexPolygon;
Get normals at control points
BezierPtrPatchNormals[shape, patch];
Expand patch by evaluating control point rows, then spitting out polygons columnwise
FOR i:
NAT
IN [0..4)
DO
FOR j:
NAT
IN [0..4)
DO
IF ctlPtRow[j] = NIL THEN ctlPtRow[j] ← NEW[ VertexInfo ];
ctlPtRow[j].coord ← vertex[patch.vtxPtr[i*4 + j]]^;
ctlPtRow[j].shade ← shade[patch.vtxPtr[i*4 + j]]^;
ENDLOOP;
row[i] ← RowEval[ ctlPtRow[0], ctlPtRow[1], ctlPtRow[2], ctlPtRow[3], nPrSide+1 ];
ENDLOOP;
colA ← RowEval[ row[0][0], row[1][0], row[2][0], row[3][0], nPrSide+1 ];
FOR i: NAT IN [0..nPrSide] DO outVtx[i+vtxCnt] ← colA[i]; ENDLOOP; -- store vertices
vtxCnt ← vtxCnt + nPrSide+1;
FOR i:
NAT
IN [1..nPrSide]
DO
colB ← RowEval[ row[0][i], row[1][i], row[2][i], row[3][i], nPrSide+1 ];
FOR j: NAT IN [0..nPrSide] DO outVtx[j+vtxCnt] ← colB[j]; ENDLOOP; -- store vertices
vtxCnt ← vtxCnt + nPrSide+1;
FOR j:
NAT
IN [1..nPrSide]
DO
IF outPatch[ptchCnt] = NIL THEN outPatch[ptchCnt] ← NEW[PtrPatch];
outPatch[ptchCnt].vtxPtr ← NEW[NatSequence[4]];
outPatch[ptchCnt].vtxPtr[0] ← (nPrSide+1) * (i-1) + j-1;
outPatch[ptchCnt].vtxPtr[1] ← (nPrSide+1) * (i-1) + j;
outPatch[ptchCnt].vtxPtr[2] ← (nPrSide+1) * i + j;
outPatch[ptchCnt].vtxPtr[3] ← (nPrSide+1) * i + j-1;
outPatch[ptchCnt].type ← outputType;
outPatch[ptchCnt].oneSided ← patch.oneSided;
outPatch[ptchCnt].nVtces ← 4;
outPatch[ptchCnt].clipState ← patch.clipState;
outPatch[ptchCnt].props ← patch.props;
ptchCnt ← ptchCnt + 1;
ENDLOOP;
colA ← colB;
ENDLOOP;
outVtx.length ← nVtces;
outPatch.length ← nPrSide*nPrSide;
RETURN[ outVtx, outPatch ];
};
BezierCurveDivide:
PUBLIC PROC[v0, v1, v2, v3:
REF VertexInfo]
RETURNS[pt:
REF VertexInfoSequence] ~ {
DeCasteljau subdivision algorithm
tempPt: REF VertexInfo;
pt ← NEW[ VertexInfoSequence[7] ]; pt.length ← 7;
pt[0] ← NEW[ VertexInfo ← v0^ ]; pt[6] ← NEW[ VertexInfo ← v3^ ];
pt[1] ← VtxShapeMidPt[v0, v1]; pt[5] ← VtxShapeMidPt[v2, v3];
tempPt ← VtxShapeMidPt[v1, v2];
pt[2] ← VtxShapeMidPt[pt[1], tempPt]; pt[4] ← VtxShapeMidPt[tempPt, pt[5]];
pt[3] ← VtxShapeMidPt[pt[2], pt[4]];
};
VtxShapeMidPt:
PROC[v0, v1:
REF VertexInfo]
RETURNS[
REF VertexInfo] ~ {
PROC[v0, v1: REF VertexInfo] RETURNS[REF VertexInfo]
shape: REF ShapeInstance ← NARROW[ Atom.GetPropFromList[v0.props, $Shape] ];
lerpProc: VertexInfoProc ← IF shape # NIL THEN shape.shadingClass.lerpVtxAux ELSE NIL;
v: REF VertexInfo ← NEW[VertexInfo];
v.coord.x ← (v0.coord.x + v1.coord.x) / 2;
v.coord.y ← (v0.coord.y + v1.coord.y) / 2;
v.coord.z ← (v0.coord.z + v1.coord.z) / 2;
v.shade.r ← (v0.shade.r + v1.shade.r) / 2;
v.shade.g ← (v0.shade.g + v1.shade.g) / 2;
v.shade.b ← (v0.shade.b + v1.shade.b) / 2;
IF lerpProc #
NIL
THEN {
-- get auxiliary info from supplied proc
data: LORA ← LIST[ v0.aux, v1.aux, NEW[REAL ← .5], NEW[REAL ← .5] ];
v^ ← lerpProc[ NIL, v^, data];
}
ELSE v.aux ← v0.aux;
v.props ← v0.props;
RETURN[v];
};
BezierSubdivideExpand:
PROC [shape:
REF ThreeDBasics.ShapeInstance, patch:
REF PtrPatch]
RETURNS [
REF VertexInfoSequence,
REF PtrPatchSequence] ~{
vertex: REF ThreeDBasics.VertexSequence ←shape.vertex;
shade: REF ThreeDBasics.ShadingSequence ← shape.shade;
outVtx: REF VertexInfoSequence ← NEW [ VertexInfoSequence [7*7] ];
outPatch: REF PtrPatchSequence ← NEW[PtrPatchSequence [4]];
row: ARRAY [0..4) OF REF VertexInfoSequence;
ctlPtRow:
ARRAY [0..4)
OF
REF VertexInfo;
Expand patch by evaluating control point rows, then spitting out polygons columnwise
FOR i:
NAT
IN [0..4)
DO
FOR j:
NAT
IN [0..4)
DO
IF ctlPtRow[j] = NIL THEN ctlPtRow[j] ← NEW[ VertexInfo ];
ctlPtRow[j].coord ← vertex[patch.vtxPtr[i*4 + j]]^;
ctlPtRow[j].shade ← shade[patch.vtxPtr[i*4 + j]]^;
ENDLOOP;
row[i] ← BezierCurveDivide[ ctlPtRow[0], ctlPtRow[1], ctlPtRow[2], ctlPtRow[3] ];
ENDLOOP;
FOR i:
NAT
IN [0..7)
DO
vtces:
REF VertexInfoSequence ← BezierCurveDivide[
row[0][i], row[1][i], row[2][i], row[3][i]
];
FOR j:
NAT
IN [0..7)
DO
outVtx[i*7 + j] ← NEW[ VertexInfo ← vtces[j]^ ];
ENDLOOP;
ENDLOOP;
FOR i:
NAT
IN [0..4)
DO
base: NAT ← (i / 2) * 21 + (i MOD 2) * 3; -- {0, 3, 21, 24}, least corners of 7x7 array
IF outPatch[i] = NIL THEN outPatch[i] ← NEW[PtrPatch];
outPatch[i].vtxPtr ← NEW [NatSequence[16]];
outPatch[i].type ← patch.type;
outPatch[i].oneSided ← patch.oneSided;
outPatch[i].nVtces ← 16;
outPatch[i].clipState ← patch.clipState;
outPatch[i].props ← patch.props;
FOR j:
NAT
IN [0..4)
DO
FOR k:
NAT
IN [0..4)
DO
outPatch[i].vtxPtr[(3-j)*4+k] ← base + 7*j + k; -- count along rows, jump by 7 to next row
ENDLOOP;
ENDLOOP;
ENDLOOP;
outVtx.length ← 7*7;
outPatch.length ← 4;
RETURN[outVtx, outPatch];
};