perm filename GEOMES.DOC[GEM,BGB] blob sn#032382 filedate 1973-03-25 generic text, type T, neo UTF8

00100 STANFORD ARTIFICIAL INTELLIGENCE LABORATORY MARCH 1973 00200 AIM - XX. 00300 00400 draft - draft - draft - draft - draft - draft - draft - draft - draft 00500 00600 GEOMES - GEOMETRIC MODELING EMBEDDED IN SAIL. 00700 00800 00900 Bruce g. Baumgart 01000 01100 01200 ABSTRACT: 01300 01400 This paper explains the SAIL accessible subroutine package 01500 called GEOMES. Using GEOMES, arbitrary polyhedron models can be 01600 contructed; moved about and viewed in perspective with hidden lines 01700 eliminated. In addition to polyhedra; GEOMES provides models for 01800 cameras and images so that simulators relevant to computer vision, 01900 problem solving, and animation can be constructed. 02000 02100 02200 FIRST EXPLAINATION - 02300 SECOND EXPLAINATION - 02400 THIRD EXPLAINATION - 02500 02600 - DATA STRUCTURE. 02700 - POLYHEDRON OPERATIONS. 02800 - EUCLIDEAN TRANSFORMATIONS. 02900 - IMAGE OPERATIONS. 03000 - EXERCISES. 03100 03200 SUMMARY GEOMES PRIMITIVES. 03300 03310 SHORT EXAMPLES. 03400 EXTENDED EXAMPLES. 03500 1. Tower Planner. 03600 2. Insect Walker. 03700 3. Newton Blocks. 00100 BEGIN "TEST1" 00200 DEFINE !="COMMENT"; 00300 DEFINE π="3.1415927"; 00400 REQUIRE "⊂⊃⊂⊃" DELIMITERS; 00500 REQUIRE "GEOMES.HDR" SOURCE_FILE; 00600 00700 INTEGER B1,B2,F,E,V,V0,T; 00800 INTEGER WORLD,WINDOW,CAMERA; 00900 01000 ! UNIVERSE CREATION; 01100 01200 WORLD ← MKWORLD; ! MAKE A WORLD; 01300 WINDOW ← MKWINDOW; ! MAKE A WINDOW; 01400 CAMERA ← MKCAMERA; ! MAKE A CAMERA; 01500 BATT(WORLD,WINDOW); ! BODY-ATTACH WORLD TO WINDOW; 01600 BATT(CAMERA,WINDOW); ! BODY-ATTACH CAMERA TO WINDOW; 01700 01800 ! BODY CREATION; 01900 02000 B1 ← MKCUBE(4.0,1.0,2.0); ! MAKE RECTANGULAR PRISM; 02100 B2 ← MKCOPY(B1); ! COPY THE PRISM; 02200 02300 ! ACTION; 02400 02500 FOR T←1 STEP 1 UNTIL 30 DO 02600 OUTSTR(13&10); ! FLUSH THE PAGE PRINTER; 02700 TRANSLATE(B1,0,0,4); ! 4 FEET +Z TOWARDS CAMERA; 02800 ROTATE(B2,π/8,π/8,0); ! ROTATION ABOUT X & Y AXES; 02900 WHILE TRUE DO 03000 BEGIN 03100 ROTATE(B1,0,-π/17,0); ! ROTATION CW ABOUT Y-AXIS; 03200 FOR T←1 STEP 1 UNTIL 40 DO 03300 BEGIN 03400 ROTATE(B1,π/20,0,0); ! ROTATION CCW ABOUT X-AXIS; 03500 ROTATE(B2,0,π/16,0); ! ROTATION CCW ABOUT Y-AXIS; 03600 SHOW2(WINDOW,1); ! DISPLAY A SIMULATED IMAGE; 03700 IF INCHRS≥1 THEN DONE; ! EXIT ON TYPE-ANY-KEY; 03800 END; 03900 END; 04000 04100 END "TEST1"; BGB 19 MARCH 1973. 00100 I. FIRST EXPLAINATION - RUNNING GEOMES. 00200 00300 This first explaination presents a small and restricted 00400 subset of GEOMES for construction and animation using bricks. Please 00500 now read the example program, TEST1. In the example, GEOMES is 00600 declared by requiring the source file GEOMES.HDR[SAI,BGB] under horse 00700 shoe delimiters. When executed, TEST1 displays one cubic brick 00800 tumbling around another. 00900 01000 01100 1st - DATA STRUCTURE: 01200 01300 GEOMES has a representation for the things called "world", 01400 "window", "camera" and "body"; such things are always referred to by 01500 an integer pointer. A world is a set of bodies; a camera is a camera 01600 model; a window ties pairs of cameras and worlds together; and a body 01700 is a model of a polyhedron composed of faces, edges and vertices. The 01800 only kind of body available is a rectangular right prism. To get your 01900 data structure initialized, write the following instructions: 02000 02100 WORLD ← MKWORLD; make world. 02200 WINDOW ← MKWINDOW; make window. 02300 CAMERA ← MKCAMERA; make camera. 02400 BATT(WORLD,WINDOW); 02500 BATT(CAMERA,WINDOW); 02600 02700 02800 1st - POLYHEDRON OPERATIONS: 02900 03000 BODY ← MKCUBE(XSIDE,YSIDE,ZSIDE); make cubic solid. 03100 BODY ← MKCOPY(BODY); make a copy. 03200 03300 The routine MKBODY generates a rectangular right prism with 03400 sides of length XSIDE, YSIDE and ZSIDE. The center of the prism is 03500 initially at the world origin, (0,0,0). The arguments are real 03600 numbers representing feet. The initial camera is located sixteen feet 03700 above the X-Y plane and is looking down with a 12.5 millimeter lens, 03800 which means that any block with sides less than 20 feet will be in 03900 view. The routine MKCOPY will return a copy of its argument, the new 04000 body will have the same location and orientation as the old one, and 04100 should be moved before a hidden line elimination. 04200 04300 WHOLE ← BATT(PART,WHOLE); body attach. 04400 PART ← BDET(PART); body detach. 04500 04600 The BATT routine attachs one body to another so that when 04700 something is moved or copied all its parts will be moved or copied 04800 too. Naturally, parts may have subparts and so on. A body is freed 04900 from its role as a part of something by the BDET routine. 00100 1st - EUCLIDEAN TRANSFORMATIONS: 00200 00300 TRANSLATE(OBJECT,DELTAX,DELTAY,DELTAZ); 00400 ROTATE(OBJECT,ABOUTX,ABOUTY,ABOUTZ); 00500 00600 The TRANSLATE routine takes four arguments, the first 00700 argument is the integer pointing at the thing to be translated, the 00800 next three arguments are real numbers indicating a displacement in 00900 feet parallel to the X, Y and Z world axes respectively. The world 01000 frame of reference is right handed and orthogonal. 01100 01200 The ROTATE routine takes four arguments, the first argument 01300 is the integer pointing at the thing to be rotated, and the next 01400 three arguments are real numbers indicating a angular displacement in 01500 radians about the X, Y and Z world axes respectively. The positive 01600 direction of rotation is counterclockwise; which is the so called 01700 right hand rule convention. 01800 01900 02000 1st - IMAGE OPERATIONS: 02100 02200 INTEGER PROCEDURE SHOW1 (INTEGER WINDOW,GLASS); 02300 INTEGER PROCEDURE SHOW2 (INTEGER WINDOW,GLASS); 02400 02500 There are two simple display operations: SHOW1 and SHOW2. 02600 The SHOW1 routine displays all the edges appearing in the window. The 02700 SHOW2 routine performs a hidden line elimination and displays only 02800 the portions of edges that are not occultated. Both routines take two 02900 arguments, the first argument is the window to be displayed and the 03000 second argument is the number, 0 to 15, of the III piece of glass to 03100 which the display buffer is sent. 03200 03300 03400 1st - EXERCISES: 03500 03600 1. Make the tower shown in the figure using 1,2,4 bricks. 03700 2. Make a table with four chairs. (use the BATT and MKCOPY). 03800 3. Make a simulation of a small bouncing cube. 00100 SECOND EXPLAINATION. 00200 00300 2nd - DATA STRUCTURE. 00400 00500 The GEOMES data structure is implemented as twelve word 00600 blocks containing pointers and data in the fashion usual to graphics 00700 and simulation; an introduction to this technology can be found in 00800 Knuth. The language of implementation is PDP-10 machine code, and 00900 although the data and subroutines discussed below are accessible from 01000 SAIL, with the exception of CORGET, no SAIL routines are called by 01100 GEOMES routines. In particular, GEOMES emphatically has nothing to do 01200 with LEAP. 01300 01400 The twelve word blocks of GEOMES are called "nodes". Nodes 01500 are referred to by their actual machine address in the user core 01600 image, which is an integer called a "link". Thus the subroutines that 01700 take nodes as arguments or return nodes as values pass links rather 01800 than the nodes themselves. In SAIL, the user core image can be 01900 accessed as a special array named MEMORY. Using the MEMORY feature of 02000 SAIL, the GEOMES.HDR defines names for where links and data are 02100 stored relative to the origin of a node. 02200 00100 2nd - POLYHEDRON OPERATIONS. 00100 2nd - EUCLIDEAN TRANSFORMATIONS. 00100 2nd - IMAGE OPERATIONS. 00100 NODE ← MKNODE(INTEGER TYP); 00200 NIL ← KLNODE(INTEGER NODE); 00300 00400 WORLD ← MKWORLD; 00500 WINDOW ← MKWINDOW; 00600 CAMERA ← MKCAMERA; 00700 LO ← MKLOCOR; 00800 00900 B ← MKB(WORLD); 01000 NIL ← KLB(WORLD); 01100 NIL ← KLBFEV(WORLD); 01200 01300 F ← MKF(B); 01400 E ← MKE(B); 01500 V ← MKV(B); 01600 01700 NIL ← WING(E1,E2); 01800 BOOL ← LINKED(Q1,Q2); 01900 02000 E ← ECW(FEV,FEV); 02100 E ← ECCW(FEV,FEV); 02200 FV ← OTHER(E,FV);