<> <> <> <> DIRECTORY Atom USING [ GetPropFromList, PropList, PutPropOnList, RemPropFromList ], Real USING [ Fix ], Rope USING [ Cat, Concat, Equal, ROPE ], Convert USING [ RopeFromInt, RopeFromReal ], Basics USING [ BITOR, BITAND ], RealFns USING [ AlmostEqual, SqRt ], G3dVector USING [ Add, Cross, Dot, Length, IntersectTwoLines2d, Line2d, Mul, Negate, Normalize, Sub ], G3dMatrix USING [ Mul, Transform, TransformVec ], G3dSpline USING [ Coeffs, Position, CoeffsFromBezier ], ScanConvert USING [ justNoticeable ], ThreeDBasics USING [ AllOut, ClipState, Context, Error, FacingDir, GetSurfaceType, NatSequence, NoneOut, OutCode, Patch, PatchProc, PatchSequence, Pair, PtrPatch, PtrPatchSequence, RealSequence, RegisterSurfaceType, RGB, ShadingSequence, ShadingValue, ShapeClass, ShapeInstance, ShapeProc, SixSides, Triple, TripleSequence, Vertex, VertexInfo, VertexInfoProc, VertexInfoSequence, VertexSequence, Xfm3D ], ShapeUtilities USING [ GetClipCodeForPt, GetPatch, GetVtxNmls, GetVtxShades, ReleasePatch, XfmPtToDisplay, XfmPtToEyeSpace, XfmToEyeSpace ], SurfaceRender USING [ GetPtrPatchClipState, OutputPolygon ]; BezierFromPolyProcs: CEDAR MONITOR IMPORTS Atom, Basics, Convert, G3dMatrix, G3dSpline, G3dVector, SurfaceRender, ThreeDBasics, Real, RealFns, Rope, ShapeUtilities = BEGIN <> ROPE: TYPE ~ Rope.ROPE; NatSequence: TYPE ~ ThreeDBasics.NatSequence; Pair: TYPE ~ ThreeDBasics.Pair; Triple: TYPE ~ ThreeDBasics.Triple; TripleSequence: TYPE ~ ThreeDBasics.TripleSequence; RGB: TYPE ~ ThreeDBasics.RGB; RealSequence: TYPE ~ ThreeDBasics.RealSequence; Context: TYPE ~ ThreeDBasics.Context; SixSides: TYPE ~ ThreeDBasics.SixSides; Xfm3D: TYPE ~ ThreeDBasics.Xfm3D; ShapeInstance: TYPE ~ ThreeDBasics.ShapeInstance; Patch: TYPE ~ ThreeDBasics.Patch; PatchSequence: TYPE ~ ThreeDBasics.PatchSequence; PatchProc: TYPE ~ ThreeDBasics.PatchProc; PtrPatch: TYPE ~ ThreeDBasics.PtrPatch; PtrPatchSequence: TYPE ~ ThreeDBasics.PtrPatchSequence; Vertex: TYPE ~ ThreeDBasics.Vertex; VertexInfo: TYPE ~ ThreeDBasics.VertexInfo; <> VertexInfoSequence: TYPE ~ ThreeDBasics.VertexInfoSequence; VertexInfoProc: TYPE ~ ThreeDBasics.VertexInfoProc; ShadingValue: TYPE ~ ThreeDBasics.ShadingValue; ShapeClass: TYPE ~ ThreeDBasics.ShapeClass; ShapeProc: TYPE ~ ThreeDBasics.ShapeProc; ClipState: TYPE ~ ThreeDBasics.ClipState; OutCode: TYPE ~ ThreeDBasics.OutCode; AllOut: OutCode ~ ThreeDBasics.AllOut; NoneOut: OutCode ~ ThreeDBasics.NoneOut; FacingDir: TYPE ~ ThreeDBasics.FacingDir; LORA: TYPE = LIST OF REF ANY; MidPtProc: TYPE ~ PROC[v0, v1: REF VertexInfo] RETURNS[REF VertexInfo]; 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 ]; <> 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]; <> 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 VertexInfo, t: ARRAY[0..3) OF TangentSet ]; NatSequenceSequence: TYPE ~ RECORD [ length: NAT _ 0, s: SEQUENCE maxLength: NAT OF REF NatSequence ]; <> 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; 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; <> minCosToAlignOpen: REAL _ 0.707; -- Align open edges if they meet at > 45 degrees cosMaxDihedral: REAL _ 0.707; -- max dihedral angle between control surfaces unitizeNormals: BOOLEAN _ FALSE; -- treat all polygons equally when making vertex normal fixDihedrals: BOOLEAN _ TRUE; -- allows dihedral fixing to be turned off ref1third: REF REAL _ NEW[REAL _ 1.0/3.0]; ref2thirds: REF REAL _ NEW[REAL _ 2.0/3.0]; refOne: REF REAL _ NEW[REAL _ 1.0]; refMinusOne: REF REAL _ NEW[REAL _ -1.0]; <> 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] < ScanConvert.justNoticeable THEN RETURN [0.0] ELSE RETURN[result]; }; DiffPosns: PROC[vtx1, vtx2: Vertex, space: ATOM _ NIL] RETURNS[Triple] ~ { <> 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] ~ { <> <> slope _ Cross[ Cross[normal, edge], normal ]; slope _ ScaleTangent[ slope, edge ]; }; ScaleTangent: PROC[tangent, edgeDir: Triple] RETURNS[Triple] ~ { <> 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: REF Context, p: REF PatchSequence, c: REF CornerSeqSeq _ NIL] RETURNS[REF PatchSequence, REF CornerSeqSeq] ~ { z: REF RealSequence _ NEW[RealSequence[p.length]]; pOut: REF PatchSequence _ NEW [PatchSequence[p.length]]; cOut: REF CornerSeqSeq _ NEW [CornerSeqSeq[p.length]]; <> 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]; }; ValidatePatchPoly: ShapeProc ~ { <> doAlways: BOOLEAN _ IF data # NIL THEN TRUE ELSE FALSE; IF GetProp[shape.fixedProps, $VtxInfoComputed] = NIL THEN ShapeUtilities.GetVtxNmls[context, shape]; -- calculate normals if not read in <> IF shape.vtcesInValid THEN { xfm: Xfm3D _ G3dMatrix.Mul[shape.position, context.eyeSpaceXfm]; << Transform vertices to eyespace, get clip state of vertices and whole shape>> shape.clipState _ ShapeUtilities.XfmToEyeSpace[ context, shape ]; <> IF shape.clipState # out THEN FOR i: NAT IN [0..shape.shade.length) DO OPEN shape.shade[i]; -- transform normal vectors [ [exn, eyn, ezn] ] _ G3dMatrix.TransformVec[ [xn, yn, zn] , xfm]; ENDLOOP; IF shape.surface # NIL THEN { -- get clipping info for patches patch: REF PtrPatchSequence _ NARROW[shape.surface]; FOR i: NAT IN [0..shape.numSurfaces) DO IF patch[i] # NIL THEN IF shape.clipState = in THEN patch[i].clipState _ in -- unclipped, inside ELSE IF shape.clipState = clipped -- evaluate clipping tags THEN SurfaceRender.GetPtrPatchClipState[ shape, patch[i] ] ELSE patch[i].clipState _ out; ENDLOOP; }; shape.vtcesInValid _ FALSE; }; IF shape.shadingInValid AND (shape.clipState # out OR doAlways) THEN ShapeUtilities.GetVtxShades[ context, shape ]; shape.shadingInValid _ FALSE; RETURN[shape]; }; 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; }; <> DisplayPatchEdges: PROC[context: REF Context, patch: REF Patch, corner: REF CornerSeq] ~ { shape: REF ShapeInstance _ NARROW[ Atom.GetPropFromList[patch.props, $Shape] ]; xfm: Xfm3D _ G3dMatrix.Mul[shape.position, context.eyeSpaceXfm]; clr: RGB _ shape.shadingClass.color; npts: NAT _ 8; FOR i: NAT IN [0..patch.nVtces) DO j: NAT _ (i+1) MOD patch.nVtces; outP: REF Patch _ ShapeUtilities.GetPatch[npts]; outState: OutCode _ AllOut; inState: OutCode _ NoneOut; coeffs: G3dSpline.Coeffs _ GetEdgeCurveBez[ -- vtx1, vtx2, outdir1, indir2 patch[i], patch[j], corner[i], corner[j] ]; FOR k: NAT IN [0..npts) DO OPEN outP[k].coord; t: REAL _ 1.0 * k / (npts-1); [[x, y, z]] _ G3dSpline.Position[coeffs, t]; [[ex, ey, ez], clip] _ ShapeUtilities.XfmPtToEyeSpace[context, [x, y, z], xfm]; clip _ ShapeUtilities.GetClipCodeForPt[ context, [ex, ey, ez] ]; IF clip = NoneOut THEN [[sx, sy, sz]] _ ShapeUtilities.XfmPtToDisplay[context, [ex, ey, ez]]; outState _ LOOPHOLE[ Basics.BITAND[LOOPHOLE[outState], LOOPHOLE[clip]] ]; inState _ LOOPHOLE[ Basics.BITOR[LOOPHOLE[inState], LOOPHOLE[clip]] ]; [outP[k].shade.er, outP[k].shade.eg, outP[k].shade.eb] _ clr; -- use shape color ENDLOOP; outP.type _ $PolyLine; outP.props _ patch.props; outP.nVtces _ npts; outP.clipState _ IF inState = NoneOut THEN in ELSE IF outState # NoneOut THEN out ELSE clipped; [outP] _ SurfaceRender.OutputPolygon[context, outP]; ENDLOOP; IF patch # NIL THEN ShapeUtilities.ReleasePatch[patch]; -- end of life for patch }; <> InitClasses: PROC[] ~ { -- register procedures for basic surface types standardClass: ShapeClass _ ThreeDBasics.GetSurfaceType[$ConvexPolygon]; standardClass.type _ $PolygonToBezier; standardClass.validate _ ValidatePolyToBezier; standardClass.displayPatch _ DisplayPatchBezier; ThreeDBasics.RegisterSurfaceType[standardClass, $PolygonToBezier]; }; <> DisplayPatchBezier: PatchProc ~ { shape: REF ShapeInstance _ NARROW[ Atom.GetPropFromList[patch.props, $Shape] ]; patchNo: NAT _ NARROW[ Atom.GetPropFromList[patch.props, $PatchNo], REF NAT ]^; corners: REF CornerSeqSeq _ NARROW[ GetProp[shape.fixedProps, $PatchCorners] ]; patch.type _ $PolygonToBezier; ConvertPolygonToBezier[context, patch, corners[patchNo] ]; -- convert to patch, display RETURN[ NIL ]; }; ValidatePolyToBezier: ShapeProc ~ { <> doEyeSpace: BOOLEAN _ shape.vtcesInValid; -- grab before reset by ValidatePatchPoly shape _ ValidatePatchPoly[context, shape]; -- Update shading and transform matrices IF GetProp[shape.fixedProps, $PatchCorners] = NIL THEN shape _ GetTangents[context, shape]; -- calculate tangent vectors if not read in RETURN[ shape ]; }; GetEdgeCurveBez: PROC[p1, p2: VertexInfo, 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: VertexInfo, c1, c2: Corner] RETURNS[b0, b1, b2, b3: Triple] ~ { <> 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 ]; <> <> <> <> <<];>> }; XfmAndClip: PROC[context: REF Context, patch: REF Patch] ~ { <> shape: REF ShapeInstance _ NARROW[ Atom.GetPropFromList[patch.props, $Shape] ]; xfm: Xfm3D _ G3dMatrix.Mul[shape.position, context.eyeSpaceXfm]; FOR i: NAT IN [0..patch.nVtces) DO OPEN patch[i].coord; [[ ex, ey, ez]] _ G3dMatrix.Transform[ [x, y, z], xfm ]; clip _ ShapeUtilities.GetClipCodeForPt[context, [ ex, ey, ez] ]; IF clip = NoneOut THEN [ [sx, sy, sz] ] _ ShapeUtilities.XfmPtToDisplay[ context, [ex, ey, ez], shape ]; ENDLOOP; }; ConvertPolygonToBezier: PROC[ context: REF Context, patch: REF Patch, corner: REF CornerSeq ] ~ { <> shape: REF ShapeInstance _ NARROW[ Atom.GetPropFromList[patch.props, $Shape] ]; IF corner.length > 4 THEN { SliceUpBezier[ context, patch, corner ]; RETURN[]; }; IF shape.shadingClass.shadingType = $Lines THEN { [] _ DisplayPatchEdges[context, patch, corner]; RETURN[]; }; IF patch.nVtces = 3 THEN DisplayTriangleAsBezier[ context, patch, corner ] <> ELSE DisplayQuadrilateralAsBezier[ context, patch, corner ]; }; SliceUpBezier: PROC[ context: REF Context, patch: REF Patch, corners: REF CornerSeq ] ~ { shape: REF ShapeInstance _ NARROW[ Atom.GetPropFromList[patch.props, $Shape] ]; lerpProc: VertexInfoProc _ IF shape # NIL THEN shape.shadingClass.lerpVtxAux ELSE NIL; outPatch: REF PatchSequence _ NEW [PatchSequence[(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] _ ShapeUtilities.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 _ undetermined; 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 ENDLOOP; }; DisplayTriangleWithTangents: PROC[ context: REF Context, patch: REF Patch, corner: REF CornerSeq ] ~ { tanClass: ShapeClass; tangents: REF TangentSeq _ NEW[TangentSeq[3]]; shape: REF ShapeInstance _ NARROW[ GetProp[patch.props, $Shape] ]; xfm: Xfm3D _ G3dMatrix.Mul[shape.position, 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 _ ThreeDBasics.GetSurfaceType[ $PolygonWithTangents ]; patch _ tanClass.displayPatch[ context, patch, tangents ]; }; DisplayTriangleAsBezier: PROC[ context: REF Context, patch: REF Patch, corner: REF CornerSeq ] ~ { doubleCornerFound: BOOLEAN _ FALSE; p: REF Patch _ ShapeUtilities.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 ThreeDBasics.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 ThreeDBasics.Error[[$MisMatch, "extra doubled vertex"]]; }; ENDLOOP; p.type _ patch.type; p.oneSided _ patch.oneSided; p.nVtces _ 4; p.clipState _ patch.clipState; p.dir _ undetermined; p.props _ patch.props; DisplayQuadrilateralAsBezier[ context, p, c ]; }; DisplayQuadrilateralAsBezier: PROC[ context: REF Context, patch: REF Patch, corner: REF CornerSeq ] ~ { <> <> <<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 _ ShapeUtilities.GetPatch[16]; bezClass: ShapeClass; FOR i: NAT IN [0..4) DO IF corner[i].double THEN SIGNAL ThreeDBasics.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] ]; <> 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 _ undetermined; b.props _ patch.props; XfmAndClip[context, b]; -- transform to eyespace and get clip state bezClass _ ThreeDBasics.GetSurfaceType[ $Bezier ]; b _ bezClass.displayPatch[ context, b ]; IF b # NIL THEN ShapeUtilities.ReleasePatch[b]; -- end of life for patch IF patch # NIL THEN ShapeUtilities.ReleasePatch[patch]; -- end of life for patch }; BoundaryRow: PROC[ context: REF Context, p1, p2: VertexInfo, c1, c2: Corner ] RETURNS[v0, v1, v2, v3: VertexInfo] ~ { <> InnerShades: PROC[ s0, s3: ShadingValue ] RETURNS[ s1, s2: ShadingValue ] ~ { 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; }; shape: REF ShapeInstance _ NARROW[ Atom.GetPropFromList[p1.props, $Shape] ]; lerpProc: VertexInfoProc _ IF shape # NIL THEN shape.shadingClass.lerpVtxAux ELSE NIL; 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]; IF lerpProc # NIL THEN { -- interpolation of vtx.aux, done remotely since type not available data: LORA _ LIST[ v0.aux, v3.aux, ref1third, ref2thirds ]; v2 _ lerpProc[ NIL, v2, data]; data _ LIST[ v0.aux, v3.aux, ref2thirds, ref1third ]; v1 _ lerpProc[ NIL, v1, data]; }; v1.props _ v2.props _ p1.props; }; InteriorPt: PROC[ context: REF Context, cornerPt, adj1, adj2: VertexInfo, corner: Corner ] RETURNS[ interiorPt: VertexInfo ] ~ { <> shape: REF ShapeInstance _ NARROW[ Atom.GetPropFromList[cornerPt.props, $Shape] ]; lerpProc: VertexInfoProc _ IF shape # NIL THEN shape.shadingClass.lerpVtxAux ELSE NIL; 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; IF lerpProc # NIL THEN { -- interpolation of vtx.aux, done remotely since type not available data: LORA _ LIST[ adj1.aux, adj2.aux, refOne, refOne ]; interiorPt _ lerpProc[ NIL, interiorPt, data]; -- sum _ adj1.aux + adj2.aux data _ LIST[ interiorPt.aux, cornerPt.aux, refOne, refMinusOne ]; -- sum - cornerPt.aux interiorPt _ lerpProc[ NIL, interiorPt, data]; }; interiorPt.props _ cornerPt.props; }; BuildBezierData: PROC[ shape: REF ShapeInstance, corners: REF CornerSeqSeq ] ~ { polyCorners: REF CornerSeqSeq _ NEW[ CornerSeqSeq[shape.numSurfaces] ]; surface: REF PtrPatchSequence _ NARROW[shape.surface]; 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. >> <> <> <> FOR i: NAT IN [0..shape.numSurfaces) DO IF surface[i] # NIL THEN { vtxCnt: NAT _ 0; nVtces: NAT _ surface[i].nVtces; surface[i].props _ Atom.RemPropFromList[surface[i].props, $Split]; -- saves later confusion 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 _ surface[i].vtxPtr[cVtx]; -- current vertex in shape nVtx: NAT _ surface[i].vtxPtr[nextVtx]; -- at far end of edge lVtx: NAT _ surface[i].vtxPtr[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 = surface[i].vtxPtr[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 ThreeDBasics.Error[[$MisMatch, "bad corner structure"]]; EXIT; }; ENDLOOP; ENDLOOP; polyCorners[i].length _ vtxCnt; }; ENDLOOP; shape.fixedProps _ PutProp[shape.fixedProps, $PatchCorners, polyCorners]; }; CheckDihedrals: PROC[ shape: REF ShapeInstance, corners: REF CornerSeqSeq ] ~ { <> 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 ] ~ { <> 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]; < 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 NOT clockWise THEN corner[i].interiorKnot _ knot ELSE corner[i].interiorKnot2 _ knot; }; FOR v: NAT IN [0..shape.vertex.length) DO IF corners[v] # NIL THEN { -- check each vtx. vtx: REF Vertex _ shape.vertex[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.x, vtx.y, vtx.z] ]; 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.x, vtx.y, vtx.z] ]; 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 ThreeDBasics.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 ]; <> <> <> <> <> <<]>> <<];>> <> <> <> <> <> <<]>> <<];>> } ELSE corner[i].interiorKnot _ Add[ -- sum directions corner[i].inDir, corner[i].outDir ]; ENDLOOP; }; <> GetTangents: ShapeProc ~ { <> corners: REF CornerSeqSeq; <> corners _ GetNormalsAndDirections[context, shape]; -- Get vertex normals, edge directions <> ForceFourCorners[corners, shape]; <<>> <> FOR i: NAT IN [0..corners.length) DO -- sort corners to clockwise order by matching edges IF corners[i] # NIL THEN corners[i] _ SortVertex[ corners[i] ]; ENDLOOP; <> 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; <> 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: REF Context, shape: REF ShapeInstance] RETURNS[REF CornerSeqSeq] ~ { <> <> preNormaled: BOOLEAN _ GetProp[shape.fixedProps, $VertexNormalsInFile] # NIL; surface: REF PtrPatchSequence _ NARROW[shape.surface]; corners: REF CornerSeqSeq _ NEW[ CornerSeqSeq[shape.vertex.length] ]; angles: REF RealSequence _ NEW[RealSequence[8]]; IF NOT preNormaled THEN FOR i: NAT IN [0..shape.shade.length) DO -- Clear vertex normals IF shape.shade[i] # NIL THEN { OPEN shape.shade[i]; [xn, yn, zn] _ nullTriple; }; ENDLOOP; FOR i: NAT IN [0..shape.numSurfaces) DO IF surface[i] # NIL THEN { -- do for all polys nVtces: NAT _ surface[i].nVtces; smallest: NAT _ LAST[NAT]; -- smallest angle in triangle (default value harmless) IF angles.maxLength < nVtces THEN angles _ NEW[RealSequence[nVtces]]; IF NOT preNormaled THEN GetPolyNormals[shape, surface[i]]; -- get normals robustly(?) IF nVtces # 4 THEN { smallestSize: REAL; -- Find smallestSize angle within non-quadrilateral FOR cVtx: NAT IN [0..nVtces) DO vtx: NAT _ surface[i].vtxPtr[cVtx]; nVtx: NAT _ surface[i].vtxPtr[(cVtx + 1) MOD nVtces]; lVtx: NAT _ surface[i].vtxPtr[(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; }; <> FOR cVtx: NAT IN [0..nVtces) DO -- get direction vectors for each edge at vtx. vtx: NAT _ surface[i].vtxPtr[cVtx]; nVtx: NAT _ surface[i].vtxPtr[(cVtx + 1) MOD nVtces]; lVtx: NAT _ surface[i].vtxPtr[(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: DiffPosns[shape.vertex[lVtx]^, shape.vertex[vtx]^], -- dir. to incoming vertex outDir: DiffPosns[shape.vertex[nVtx]^, shape.vertex[vtx]^], -- outgoing direction double: IF cVtx = smallest THEN TRUE ELSE FALSE -- doubled (degenerate edge) ] ]; ENDLOOP; <> IF nVtces > 4 THEN SplitBigPoly[shape, surface[i], corners, angles]; }; ENDLOOP; corners.length _ shape.vertex.length; FOR i: NAT IN [0..shape.shade.length) DO -- normalize new vertex normals, store in corners IF shape.shade[i] # NIL THEN { OPEN shape.shade[i]; IF Length[ [xn, yn, zn] ] > shape.boundingRadius * .0001 THEN [[xn, yn, zn]] _ Normalize[ [xn, yn, zn] ] ELSE [xn, yn, zn] _ 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 _ [xn, yn, zn]; ENDLOOP; }; ENDLOOP; RETURN[ corners ]; }; GetAngle: PROC[ shape: REF ShapeInstance, vtx, lVtx, nVtx: NAT] RETURNS[REAL] ~ { e1: Triple _ Normalize[ DiffPosns[shape.vertex[lVtx]^, shape.vertex[vtx]^] ]; e2: Triple _ Normalize[ DiffPosns[shape.vertex[nVtx]^, shape.vertex[vtx]^] ]; 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: REF ShapeInstance, poly: REF PtrPatch, corners: REF CornerSeqSeq, angles: REF RealSequence ] ~ { <> 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, poly, corners, vtx, oVtx]; InsertEdge[shape, poly, corners, oVtx, vtx]; remainingVtces _ nVtces - increment; WHILE remainingVtces > 4 DO <> remainingVtces _ remainingVtces - increment; ENDLOOP; poly.props _ Atom.PutPropOnList[poly.props, $Split, $ItIs]; }; InsertEdge: PROC[ shape: REF ShapeInstance, poly: REF PtrPatch, corners: REF CornerSeqSeq, cVtx, oVtx: NAT ] ~ { nVtces: NAT _ poly.nVtces; vtx: NAT _ poly.vtxPtr[cVtx]; oppVtx: NAT _ poly.vtxPtr[oVtx]; nVtx: NAT _ poly.vtxPtr[(cVtx + 1) MOD nVtces]; lVtx: NAT _ poly.vtxPtr[(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: DiffPosns[shape.vertex[lVtx]^, shape.vertex[vtx]^], -- direction to inVtx outDir: DiffPosns[shape.vertex[oppVtx]^, shape.vertex[vtx]^] -- out direction ] ]; corners[vtx][i].inVtx _ oppVtx; -- fix up vtx already in sequence corners[vtx][i].inDir _ DiffPosns[shape.vertex[oppVtx]^, shape.vertex[vtx]^]; EXIT; }; ENDLOOP; <> 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: REF ShapeInstance, poly: REF PtrPatch ] ~ { <> normal: Triple _ nullTriple; nVtces: NAT _ poly.nVtces; cNmls: REF TripleSequence _ NEW[TripleSequence[nVtces]]; FOR cVtx: NAT IN [0..nVtces) DO -- get normal for each corner vtx: NAT _ poly.vtxPtr[cVtx]; nVtx: NAT _ poly.vtxPtr[(cVtx + 1) MOD nVtces]; lVtx: NAT _ poly.vtxPtr[(cVtx + nVtces - 1) MOD nVtces]; cNmls[cVtx] _ Cross[ -- in object space so do right-handed DiffPosns[ shape.vertex[lVtx]^, shape.vertex[vtx]^ ], DiffPosns[ shape.vertex[nVtx]^, shape.vertex[vtx]^ ] ]; 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.vtxPtr[cVtx]; IF shape.shade[vtx] # NIL THEN { OPEN shape.shade[vtx]; -- sum normals [[xn, yn, zn]] _ Add[[xn, yn, zn], 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: REF ShapeInstance ] ~ { surface: REF PtrPatchSequence _ NARROW[shape.surface]; 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 surface[k].nVtces > 3 AND Atom.GetPropFromList[surface[k].props, $Split] = NIL THEN { nVtces: NAT _ surface[k].nVtces; -- only triangles have doubled vertices FOR v: NAT IN [0..nVtces) DO IF surface[k].vtxPtr[v] = i THEN { cVtx _ v; oppVtx _ (v+2) MOD nVtces; -- get opposing vtx. EXIT; }; ENDLOOP; IF corners[surface[k].vtxPtr[oppVtx]].length = 3 -- find a 3-poly vertex THEN { <> InsertEdge[shape, surface[k], corners, cVtx, oppVtx]; InsertEdge[shape, surface[k], corners, oppVtx, cVtx]; surface[k].props _ Atom.PutPropOnList[surface[k].props, $Split, $ItIs]; EXIT; } ELSE IF corners[surface[k].vtxPtr[oppVtx]].length < smallestCorner THEN { smallestCorner _ corners[surface[k].vtxPtr[oppVtx]].length; polyToSplit _ k; vertexNo _ cVtx; oppVtxNo _ oppVtx; }; }; IF j = 2 THEN { InsertEdge[shape, surface[polyToSplit], corners, vertexNo, oppVtxNo]; InsertEdge[shape, surface[polyToSplit], corners, oppVtxNo, vertexNo]; surface[polyToSplit].props _ Atom.PutPropOnList[ surface[polyToSplit].props, $Split, $ItIs ]; }; ENDLOOP; }; }; ENDLOOP; }; FindContinuousEdges: PROC[ shape: REF ShapeInstance, vtx: NAT, corner: REF CornerSeq ] RETURNS[ REF CornerSeq ] ~ { <> nCorners: NAT _ corner.length; acrossFrom: REF NatSequenceSequence _ NEW[NatSequenceSequence[nCorners]]; FOR this: NAT IN [0..nCorners) DO acrossFrom[this] _ NEW[NatSequence[nCorners]]; ENDLOOP; <> 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 ThreeDBasics.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 ThreeDBasics.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; ENDCASE => { }; IF nCorners > 4 THEN AlignBigVertex[ 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, DiffPosns[shape.vertex[corner[this].outVtx]^, shape.vertex[vtx]^] ]; IF corner[last].inVtx = corner[this].outVtx THEN corner[last].inDir _ corner[this].outDir ELSE corner[last].inDir _ ScaleTangent[ corner[last].inDir, DiffPosns[shape.vertex[corner[last].inVtx]^, shape.vertex[vtx]^] ]; ENDLOOP; RETURN[ corner ]; }; AlignBigVertex: PROC[ corner: REF CornerSeq, nCorners: NAT ] ~ { <> 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; <> 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; <> 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; <> 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; }; }; SortVertex: PROC[corner: REF CornerSeq] RETURNS[REF CornerSeq] ~ { <> <> 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 ThreeDBasics.Error[[$Fatal, "Multiple open edges at a vertex not allowed"]]; ENDLOOP; IF newSeq.length > 0 THEN corner _ newSeq; RETURN[ corner ]; }; InitClasses[]; END.