DIRECTORY
Atom					USING [ GetPropFromList ],
Real					USING [ FixC ],
UserCredentials		USING [ Get ],
IO						USING [ STREAM,  PutF, rope, time, int , real, Close ],
FS						USING [ StreamOpen ],
Rope					USING [ Cat, ROPE ],
CedarProcess			USING [ DoWithPriority ],
ImagerColor			USING [ RGB ],
Vector3d				USING [ Sub, Mag, Triple	 ],
Matrix3d				USING [ Transform ],
ThreeDScenes		USING [ Context, FindShape, NewShape, ShadingSequence, SetPosition,
								 ShapeInstance, ShapeSequence, Vertex, VertexSequence ], 
ThreeDSurfaces		USING [ PtrPatchSequence ],
ShapeTwiddle		USING [ NatPair ];
ShapeTwiddleImpl: CEDAR PROGRAM
IMPORTS  Atom, Real, FS, IO, Vector3d, Rope, ThreeDScenes, UserCredentials, CedarProcess, Matrix3d
EXPORTS ShapeTwiddle

~ BEGIN

Context: TYPE ~ ThreeDScenes.Context;
ShapeTwiddleError: PUBLIC SIGNAL [reason: ATOM] = CODE;
NatPair: TYPE ~ ShapeTwiddle.NatPair;			-- RECORD [x, y: NAT];
PairSequence: TYPE ~ RECORD [SEQUENCE length: NAT OF NatPair];
Triple: TYPE ~ Vector3d.Triple;
RGB: TYPE ~ ImagerColor.RGB;
NatSequence: TYPE ~ RECORD [SEQUENCE length: NAT OF NAT];

WriteOutShape: PUBLIC PROC [context: REF Context, name, ext: Rope.ROPE _ NIL] ~ {
shape: REF ThreeDScenes.ShapeInstance _ ThreeDScenes.FindShape[ context.shapes, name ];
surface: REF ThreeDSurfaces.PtrPatchSequence _ NARROW[shape.surface];
numbered: BOOLEAN _ FALSE;
out: IO.STREAM;
IF name = NIL THEN  SIGNAL ShapeTwiddleError[$UnNamedObject];
IF ext = NIL THEN ext _ "shape";
out _ FS.StreamOpen[
fileName: Rope.Cat[name, ".", ext],
accessOptions: create, 
wDir: NARROW[ Atom.GetPropFromList[context.props, $WDir] ] 
];
out.PutF["   %g - Created by: %g at %g\n",
IO.rope[name], 
IO.rope[UserCredentials.Get[].name],
IO.time[]
];
out.PutF["   %g   %g \n", IO.int[shape.vertex.length], IO.int[shape.numSurfaces] ];
IF shape.positionInValid THEN ThreeDScenes.SetPosition[shape]; 		-- set position matrix
FOR i: NAT IN [0..shape.vertex.length) DO 
OPEN shape.vertex[i];
tx, ty, tz: REAL;
[ [tx, ty, tz] ] _ Matrix3d.Transform[ [x, y, z], shape.position];
IF numbered 
THEN out.PutF[" %g  %g   %g   %g\n", IO.int[i], IO.real[tx], IO.real[ty], IO.real[tz] ]
ELSE out.PutF["   %g   %g   %g\n", IO.real[tx], IO.real[ty], IO.real[tz] ];
ENDLOOP;
FOR i: NAT IN [0..shape.numSurfaces) DO 
out.PutF["%g     ", IO.int[surface[i].nVtces] ];
FOR j: NAT IN [0..surface[i].nVtces) DO
out.PutF["  %g", IO.int[ surface[i][j] + 1 ] ];	-- start count from one to avoid zeroes
ENDLOOP;
out.PutF["\n"];
ENDLOOP;
IO.Close[out];
};

ScaleShape: PUBLIC PROC [context: REF Context, name: Rope.ROPE, scale: REAL, 
		xRatio, yRatio, zRatio: REAL _ 1.0] ~ {
shape: REF ThreeDScenes.ShapeInstance _ ThreeDScenes.FindShape[ context.shapes, name ];
IF shape.positionInValid THEN ThreeDScenes.SetPosition[shape]; 		-- set position matrix
FOR i: NAT IN [0..shape.vertex.length) DO 
OPEN shape.vertex[i];
tx, ty, tz: REAL;
[ [tx, ty, tz] ] _ Matrix3d.Transform[ [x, y, z], shape.position];
x _ tx * scale * xRatio;
y _ ty * scale * yRatio;
z _ tz * scale * zRatio;
ENDLOOP;
};

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] ~ {	
currPos: NAT _ 0;
shape: REF ThreeDScenes.ShapeInstance _ ThreeDScenes.FindShape[ context.shapes, name ];
surface: REF ThreeDSurfaces.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 ThreeDScenes.VertexSequence; 
newShade: REF ThreeDScenes.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 ShapeTwiddleError[$ToleranceTooLarge];
FOR i: NAT IN [0..shape.vertex.length) DO					-- bucket sort vertices
index: NAT _ Real.FixC[ (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 ThreeDScenes.Vertex _ shape.vertex[i];
xBucket: NAT _ MAX[1, MIN[shape.vertex.length-1, Real.FixC[ (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 _ Vector3d.Mag[ Vector3d.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][j] _ table[surface[i][j]];
ENDLOOP;
ENDLOOP;
IF shape.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][j] # surface[i][k] THEN {
surface[i][vtx] _ surface[i][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][j]] _ table[surface[i][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[ ThreeDScenes.VertexSequence[currPos] ];
newShade _ NEW[ ThreeDScenes.ShadingSequence[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][j] _ table[surface[i][j]];
ENDLOOP;
ENDLOOP;
};
CedarProcess.DoWithPriority[background, Action];
};

CopyShape: PUBLIC PROC [context: REF Context, dstName, srcName: Rope.ROPE] 
            RETURNS[REF ThreeDScenes.ShapeInstance] ~ {
dstShape: REF ThreeDScenes.ShapeInstance _ ThreeDScenes.NewShape[dstName];
srcShape: REF ThreeDScenes.ShapeInstance _ ThreeDScenes.FindShape[ 
				       context.shapes, srcName ];
srcSurface: REF ThreeDSurfaces.PtrPatchSequence _ NARROW[srcShape.surface];
dstSurface: REF ThreeDSurfaces.PtrPatchSequence;
currPos: NAT _ 0;
shape: REF ThreeDScenes.ShapeInstance _ ThreeDScenes.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[ThreeDScenes.VertexSequence[srcShape.vertex.length] ];
FOR i: NAT IN [0..srcShape.vertex.length) DO 
dstShape.vertex[i] _ srcShape.vertex[i];  
ENDLOOP;
dstShape.shade _ NEW[ ThreeDScenes.ShadingSequence[srcShape.shade.length] ];
FOR i: NAT IN [0..srcShape.shade.length) DO  
dstShape.shade[i] _ srcShape.shade[i];  
ENDLOOP;
dstShape.surface _ NEW[ ThreeDSurfaces.PtrPatchSequence[srcShape.numSurfaces] ];
dstSurface _ NARROW[dstShape.surface, REF ThreeDSurfaces.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 ThreeDScenes.ShapeInstance] ~ {
shape: REF ThreeDScenes.ShapeInstance _ ThreeDScenes.NewShape[dstName];
shape1: REF ThreeDScenes.ShapeInstance _ ThreeDScenes.FindShape[ context.shapes, src1 ];
shape2: REF ThreeDScenes.ShapeInstance _ ThreeDScenes.FindShape[ context.shapes, src2 ];
surface1: REF ThreeDSurfaces.PtrPatchSequence _ NARROW[shape1.surface];
surface2: REF ThreeDSurfaces.PtrPatchSequence _ NARROW[shape2.surface];
surface: REF ThreeDSurfaces.PtrPatchSequence;

shape.vertex _ NEW[   				-- copy vertices
          ThreeDScenes.VertexSequence[shape1.vertex.length + shape2.vertex.length] ];
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]] _ Matrix3d.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]] _ Matrix3d.Transform[ 
[shape.vertex[i].x, shape.vertex[i].y, shape.vertex[i].z], 
shape2.position
];
ENDLOOP;
shape.shade _ NEW[ 				-- copy shading values
          ThreeDScenes.ShadingSequence[shape1.shade.length + shape2.shade.length] ];
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
       ThreeDSurfaces.PtrPatchSequence[shape1.numSurfaces + shape2.numSurfaces] ];
surface _ NARROW[shape.surface, REF ThreeDSurfaces.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][j] _ surface[i+base][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 ThreeDScenes.ShapeInstance] ~ {
currPos: NAT _ 0;
oldShape: REF ThreeDScenes.ShapeInstance _ ThreeDScenes.FindShape[
																		  context.shapes, srcName ];
shape: REF ThreeDScenes.ShapeInstance _ CopyShape[context, dstName, srcName];
surface: REF ThreeDSurfaces.PtrPatchSequence;
surface _ NARROW[shape.surface, REF ThreeDSurfaces.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 ThreeDScenes.ShapeInstance _ ThreeDScenes.FindShape[ context.shapes, 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;
};

END.
ฎShapeTwiddleImpl.mesa 
Last Edited by: Crow, March 28, 1986 4:20:57 pm PST
Types
Global Variables
Shape Manipulations
delete excess vertices, join identical ones, etc.
ส7˜
headš
œ™Jš
œ3™3
defaultš
ฯk	˜	Jšœ	œ
œ˜#Jšœ	œ
˜Jšœœ	˜Jšœœ	œ&˜?Jšœœ˜Jšœ	œ
œœ˜Jšœœ˜(Jšœœœ˜Jšœœ˜(Jšœœ˜ Jšœœ€
˜“
Jšœœ˜+Jšœœ
˜ ——
head2šœœ
˜Jšœ[˜bJšœ
˜J˜Jšœ˜J˜—
head3š
ะbi™I
ašœ	œ˜%Oš	œœ
œ
œœ
˜7Icodešœ	œฯc˜>Pšœœœœ	œ
œ
˜>Iunitšœœ˜Jšœœœ
˜Pš
œ
œœœ	œ
œ
œ˜9P˜—Nš
ฯb™š
 ™š
ฯn
œœœœœ˜QJšœœM˜WLšœ	œ#œ˜ELšœ
œœ
˜Lšœ˜Lšœœ
œœ#˜=Lšœœ
œ˜ š
œ˜Lš
œ#˜#Lš
œ˜Lšœœ/˜;Lš
œ˜—š
œ*˜*Lšœ
˜Lšœ"˜$Lšœ˜	L˜—Lšœœœ˜SJšœœ!Ÿ˜Wšœœ
œœ
˜*Lšœ˜Lšœœ
˜Lš
œB˜Bšœ
˜Lš
œ!œ	œœœ˜WLšœœœœ˜K—Lšœ
˜—šœœ
œœ
˜(Lšœœ˜0šœœ
œ˜'LšœœŸ'˜WLšœ
˜Lš
œ˜—Lšœ
˜—Lšœ˜L˜—šก
œœœœ	œœ˜wJšœœM˜WJšœœ!Ÿ˜Wšœœ
œœ
˜*Lšœ˜Lšœœ
˜Lš
œB˜BJš
œ˜Jš
œ˜Jš
œ˜Lšœ
˜—P˜Jšœ
œœ
œ˜)Jš
œœœ
œ	œ
œ
œ˜B—šกœœœœ
œœœ˜{Pš
Ÿ1™1Jšœ	œ˜JšœœM˜WLšœ	œ#œ˜ELšœœœ%˜ALšœ	œœ,˜KLšœœ!˜0Lšœœ˜)Lšœ
œ˜+šกœœ˜šœœ˜Lšœœ
˜Jš
œ%˜%Jš
œ3˜3Jšœœ
œ'˜Mš	œœ
œœŸ˜EJšœœ5˜?šœœ
˜šœ˜Jšœœ˜$Jšœ/Ÿ"˜QJšœ&Ÿ˜<Jš
œ3˜3J˜
—šœ˜JšœœŸ˜?Jš
œ˜J˜——Jšœ Ÿ˜7Jšœ˜	—š	œœ
œœŸ˜AJšœœ'˜/Jšœ	œœœ=˜VJšœŸ˜0š	œœ
œœŸ(˜SJšœœ˜šœ˜Jšœœ˜šœœ Ÿ˜;J˜J˜9J˜—Jš	œœ
œœŸ˜PJšœ œœ
œ
˜7Jšœ
˜—Jšœ
˜—Jšœ
˜—š	œœ
œœ	Ÿ˜Kš
œœ
œ
œœ
œ˜@Jš
œ%˜%Jšœ
˜—Jšœ
˜—šœœ˜%š	œœ
œœ
Ÿ)˜QJšœœ˜
š
œœ
œ
œœ
œ˜@Jšœœœ˜9šœœ˜'J˜ J˜J˜—Jšœ
˜—J˜Jšœ
˜—J˜—LšœŸ˜—Lš
œœ
œœœ
˜;š	œœ
œœŸ˜Iš
œœ
œ
œœ
œ˜@Lš
œ0˜0Lšœ
˜—Lšœ
˜—Lš
œ˜š	œœ
œœŸ-˜Sšœ
œœ˜Lš
œ(˜(Lš
œ&˜&Lš
œ˜Lš
œ˜Lš
œ˜—Lšœ
˜—Lšœ	œ)˜5Lšœœ*˜8š	œœ
œœŸ+˜LLš
œ˜Lš
œ˜Lšœ
˜—Lšœœ
˜Lš
œ˜š	œœ
œœŸ˜Ešœœ
œ˜'Lš
œ%˜%Lšœ
˜—Lšœ
˜—L˜—Pš
œ0˜0P˜—šก	œœœ!œœ
œ ˜ƒ
Jšœ
œ=˜JPšœ
œ\˜iLšœœ#œ˜KJšœœ!˜0Jšœ	œ˜Jšœœ=˜GPš
œ,˜,Pš
œ&˜&Pš
œ&˜&Pš
œ&˜&Pš
œ$˜$Pš
œ&˜&Pš
œ2˜2Pšœœ7˜Lšœœ
œœ
˜-Pš
œ*˜*Pšœ
˜—Pšœœ8˜Lš	œœ
œœ
Ÿ
˜-Pš
œ(˜(Pšœ
˜—Pšœœ:˜PPšœ
œœ"˜Kšœœ
œœ˜,Pš
œ ˜ Pšœ
˜—Pš
œ,˜,Pš
œ.˜.Pš
œ ˜ Pšœ˜Pš
œ˜—šกœœœ$œœ
œ ˜€
Jšœœ=˜GPšœœM˜XPšœœM˜XLšœ
œ#œ˜GLšœ
œ#œ˜GLšœ	œ!˜-P˜PšœœŸœV˜€
šœœ
œ˜*Pš
œ%˜%š
œR˜RPš
œ;˜;Pš
œ˜Pš
œ˜—Pšœ
˜—šœœ
œœ˜,Pš
œ:˜:š
œR˜RPš
œ;˜;Pš
œ˜Pš
œ˜—Pšœ
˜—PšœœŸœU˜‚
š	œœ
œœ
Ÿ
˜+Pš
œ#˜#Pšœ
˜—šœœ
œœ˜+Pš
œ7˜7Pšœ
˜—Pš
œ<˜<PšœœŸœS˜{Pšœ
œœ"˜Ešœœ
œœ˜*Pš
œ˜Pšœ
˜—šœœ
œœ˜*Pšœœ˜Pš
œ ˜ š	œœ
œœŸ˜IPš
œ>˜>Pšœ
˜—Pšœ
˜—Pš
œ)˜)Pš
œ˜Pšœ˜Pš
œ˜—šก
œœœ!œœ
œœ
œ ˜ก
Jšœ	œ˜Jšœ
œd˜qJšœœC˜MLšœ	œ!˜-Pšœ
œœ"˜Ešœœ
œ œœ
˜Dšœœ
œ˜-Pšœ
œ
˜Pšœ
˜—Pšœ
˜—š	œœ
œœŸ˜:šœœ
œ˜Pš
œ˜Lš
œ˜L˜—Pšœ
˜—Pš
œ˜Jšœ
˜Pš
œ˜—šกœœœœ
œ%œ˜tJšœœM˜WLš
œ ˜ Lš
œ ˜ Lš
œ!˜!š	œœ
œœŸ!˜Yšœ˜Jšœ˜Jšœ
œœ˜?—šœ˜Jšœ˜Jšœ
œœ˜?—šœ˜Jšœ˜Jšœ
œœ˜?—Jšœ
˜—P˜——Jšœ
˜—…—0*?