x軸、y軸方向の単位ベクトルをそれぞれ −→ ┌ ┐ −→ ┌ ┐ ｅ１＝│１│， ｅ２＝│０│ │０│ │１│ └ ┘ └ ┘ とします。この単位ベクトルを原点の回りにθだけ回転すると −→ ┌ ┐ −→ ┌ ┐ ｅ１’＝│ｃｏｓθ│， ｅ２’＝│−ｓｉｎθ│ │ｓｉｎθ│ │ ｃｏｓθ│ └ ┘ └ ┘ となります。2次元座標上の点P (x, y) は −→ −→ −→ ＯＰ＝ｘ・ｅ１＋ｙ・ｅ２ と表せますが、点 P を原点の回りにθだけ回転した点を P' とすると −→ −→ −→ ＯＰ’＝ｘ・ｅ１’＋ｙ・ｅ２’ ┌ ┐ ┌ ┐ ＝ｘ│ｃｏｓθ│＋ｙ│−ｓｉｎθ│ │ｓｉｎθ│ │ ｃｏｓθ│ └ ┘ └ ┘ ┌ ┐ ＝│ｘ・ｃｏｓθ−ｙ・ｓｉｎθ│ │ｘ・ｓｉｎθ＋ｙ・ｃｏｓθ│ └ ┘ ┌ ┐┌ ┐ ＝│ｃｏｓθ −ｓｉｎθ││ｘ│ │ｓｉｎθ ｃｏｓθ││ｙ│ └ ┘└ ┘ ┌ ┐ ＝│ｃｏｓθ −ｓｉｎθ│−→ │ｓｉｎθ ｃｏｓθ│ＯＰ └ ┘ となります。
3次元座標上の点を原点の回りに回転させるには、x,y,z各軸回りの 回転を組み合わせます。
世界座標系から視野座標系に変換するには以下の操作を行ないます。
┌ ┐ ┌ ┐┌ ┐ │ｘ’│ │ １ ０ ０ −ｅｘ││ｘ│ │ｙ’│＝│ ０ １ ０ −ｅｙ││ｙ│ │ｚ’│ │ ０ ０ １ −ｅｚ││ｚ│ │１ │ │ ０ ０ ０ １││１│ └ ┘ └ ┘└ ┘この平行移動によって視線ベクトルの始点は原点となります。
┌ ┐ ┌ ┐┌ ┐
│ｘ１│ │ ｃｏｓθ −ｓｉｎθ ０││ｘ’│
│ｙ１│＝│ ｓｉｎθ ｃｏｓθ ０││ｙ’│
│ｚ１│ │ ０ ０ １││ｚ’│
└ ┘ └ ┘└ ┘
cos θ = y / (x^2 + y^2)^{1/2}
sin θ = x / (x^2 + y^2)^{1/2}
┌ ┐ ┌ ┐┌ ┐
│ｘ２│＝│ １ ０ ０││ｘ１│
│ｙ２│ │ ０ ｃｏｓψ ｓｉｎψ││ｙ１│
│ｚ２│ │ ０ −ｓｉｎψ ｃｏｓψ││ｚ１│
└ ┘ └ ┘└ ┘
cos ψ = -z / (x^2 + y^2 + z^2)^{1/2}
sin ψ = (x^2 + y^2)^{1/2} / (x^2 + y^2 + z^2)^{1/2}
┌ ┐ ┌ ┐┌ ┐ │ｘ３│＝│ １ ０ ０ ││ｘ２│ │ｙ３│ │ ０ １ ０ ││ｙ２│ │ｚ３│ │ ０ ０ −１ ││ｚ２│ └ ┘ └ ┘└ ┘
┌ ┐ ┌ ┐┌ ┐ │ｘ４│＝Ｄ／ｚ３│ １ ０ ０ ││ｘ３│ │ｙ４│ │ ０ １ ０ ││ｙ３│ │ｚ４│ │ ０ ０ １ ││ｚ３│ └ ┘ └ ┘└ ┘z座標に関しては
| vec.h |
#include <stdio.h>
#include <math.h>
#ifndef __VEC_H__
#define __VEC_H__
#define NMAT 4
typedef struct _vector {
double x, y, z;
} Vector;
typedef struct _line {
Vector *start, *end;
} Line;
void vadd(Vector *a, Vector *b, Vector *c);
void vsub(Vector *a, Vector *b, Vector *c);
double dotprod(Vector *a, Vector *b);
void crossprod(Vector *a, Vector *b, Vector *c);
void smul(double s, Vector *a, Vector *b);
void vnorm(Vector *src, Vector *dst);
void vmul(double m[NMAT][NMAT], Vector *a, Vector *b);
void mmult(double a[NMAT][NMAT], double b[NMAT][NMAT], double c[NMAT][NMAT]);
void getmatrix(double m[NMAT][NMAT],Vector *p,Vector *v);
void project(Vector *a, double d, Vector *ans);
void printvec(Vector *v);
void printmatrix(double m[NMAT][NMAT]);
#endif
|
| vec.c |
#include "vec.h"
void vadd(Vector *a, Vector *b, Vector *c) {
// a + b → c
// 課題
}
void vsub(Vector *a, Vector *b, Vector *c) {
// a - b → c
// 課題
}
double dotprod(Vector *a, Vector *b) {
// a ・ b → 返す
// 課題
}
void crossprod(Vector *a, Vector *b, Vector *c) {
Vector d;
d.x = a->y * b->z - a->z * b->y;
d.y = a->z * b->x - a->x * b->z;
d.z = a->x * b->y - a->y * b->x;
*c = d;
}
void smul(double s, Vector *a, Vector *b) {
b->x = a->x * s;
b->y = a->y * s;
b->z = a->z * s;
}
void vnorm(Vector *src, Vector *dst) {
double len = sqrt(dotprod(src,src));
smul(1.0/len,src,dst);
}
void vmul(double m[NMAT][NMAT], Vector *a, Vector *b) {
Vector c;
c.x = m[0][0] * a->x + m[0][1] * a->y + m[0][2] * a->z + m[0][3];
c.y = m[1][0] * a->x + m[1][1] * a->y + m[1][2] * a->z + m[1][3];
c.z = m[2][0] * a->x + m[2][1] * a->y + m[2][2] * a->z + m[2][3];
*b = c;
}
void mmult(double a[NMAT][NMAT], double b[NMAT][NMAT], double c[NMAT][NMAT]) {
double d[NMAT][NMAT];
// a ・ b → d を計算してから dをcにコピーする
// 課題
bcopy(d,c,sizeof(double)*NMAT*NMAT);
}
void mset(double m[NMAT][NMAT],
double a00,double a01,double a02,double a03,
double a10,double a11,double a12,double a13,
double a20,double a21,double a22,double a23,
double a30,double a31,double a32,double a33) {
m[0][0]=a00; m[0][1]=a01; m[0][2]=a02; m[0][3]=a03;
m[1][0]=a10; m[1][1]=a11; m[1][2]=a12; m[1][3]=a13;
m[2][0]=a20; m[2][1]=a21; m[2][2]=a22; m[2][3]=a23;
m[3][0]=a30; m[3][1]=a31; m[3][2]=a32; m[3][3]=a33;
}
void getmatrix(double m[NMAT][NMAT],Vector *p,Vector *v) {
// 課題
}
void project(Vector *a, double d, Vector *ans) {
ans->x = d * a->x / a->z;
ans->y = d * a->y / a->z;
ans->z = a->z;
}
void printvec(Vector *v) {
printf("(%f,%f,%f)",v->x,v->y,v->z);
fflush(stdout);
}
void printmatrix(double m[NMAT][NMAT]) {
int i, j;
for (i=0; i<NMAT; ++i) {
for (j=0; j<NMAT; ++j) {
printf("%f ",m[i][j]);
}
printf("\n");
}
}
|
| x24.c |
#include <stdio.h>
#include <X11/Xos.h>
#include <X11/Xlib.h>
#include <X11/Xutil.h>
#include <time.h>
#include "vec.h"
#define TIME_SPAN 0.1
#define SCR_DIS 1.0
#define SCR_MAG 200.0
Vector points[] = {
{0,0,0},{100,0,0},{100,100,0}, {0,100,0} ,
{0,0,100},{100,0,100},{100,100,100},{0,100,100},
{100,-100,0},{0,-100,0},{50,-50,200},
};
Line lines[] = {
{ &points[0], &points[1] }, { &points[1], &points[2] }, /* 立方体 */
{ &points[2], &points[3] }, { &points[3], &points[0] },
{ &points[4], &points[5] }, { &points[5], &points[6] },
{ &points[6], &points[7] }, { &points[7], &points[4] },
{ &points[0], &points[4] }, { &points[1], &points[5] },
{ &points[2], &points[6] }, { &points[3], &points[7] },
{ &points[1], &points[8] }, { &points[8], &points[9] }, /* 四角錐 */
{ &points[9], &points[0] }, { &points[10], &points[0] },
{ &points[10], &points[1] }, { &points[10], &points[8] },
{ &points[10], &points[9] },
};
#define WIDTH 320
#define HEIGHT 240
#define NPOINTS (sizeof(points)/sizeof(Vector))
#define NLINES (sizeof(lines)/sizeof(Line))
Vector eyepos = { 800, 800, 200 };
Vector eyedir = { -4, -4, -1 };
Display *dpy;
int scr;
Window win;
GC gc;
int init_xwin(int width, int height) {
XGCValues gcv;
XSetWindowAttributes xswa;
if ((dpy = XOpenDisplay(NULL)) == NULL) {
fprintf(stderr, "cant open display\n");
exit(1);
}
scr = DefaultScreen(dpy);
xswa.background_pixel = BlackPixel(dpy,scr);
xswa.border_pixel = BlackPixel(dpy,scr);
xswa.event_mask = ExposureMask | ButtonPressMask;
win=XCreateWindow(dpy,RootWindow(dpy,scr),0,0,width,height,1,
CopyFromParent,CopyFromParent,CopyFromParent,
(CWBackPixel|CWBorderPixel|CWEventMask),&xswa);
gcv.foreground = WhitePixel(dpy,scr);
gcv.background = BlackPixel(dpy,scr);
gcv.function = GXcopy; /* GXxor; */
gc = XCreateGC(dpy,win,(GCForeground|GCBackground|GCFunction),&gcv);
XMapWindow(dpy,win);
}
void drawview(Display *dpy, Window win, GC gc,
Line *lines, int n_lines,
Vector *eyepos, Vector *eyedir,
int w, int h) {
double m[NMAT][NMAT];
Vector p, q;
int i;
getmatrix(m,eyepos,eyedir);
for (i=0; i< n_lines; ++i) {
vmul(m,lines[i].start,&p); vmul(m,lines[i].end,&q);
project(&p,SCR_MAG/SCR_DIS,&p); project(&q,SCR_MAG/SCR_DIS,&q);
XDrawLine(dpy,win,gc,(int)p.x+w/2,(int)-p.y+h/2,(int)q.x+w/2,(int)-q.y+h/2);
}
XFlush(dpy);
}
double gettime() {
struct timeval t;
gettimeofday(&t,0);
return(t.tv_sec + t.tv_usec * 1e-6);
}
int main() {
double t1,t2,t3;
init_xwin(WIDTH,HEIGHT);
XMapWindow(dpy,win);
for (;;) {
fd_set readfds, writefds, exceptfds;
struct timeval timeout;
int i;
XEvent ev;
FD_ZERO(&readfds);
FD_ZERO(&writefds);
FD_ZERO(&exceptfds);
FD_SET(ConnectionNumber(dpy),&readfds);
t2 = gettime();
t3 = TIME_SPAN - (t2 - t1);
if (t3 < 0) t3 = 0;
timeout.tv_sec = t3;
timeout.tv_usec = (t3 - timeout.tv_sec) * 1e6;
i = select(getdtablesize(),&readfds,&writefds,&exceptfds,&timeout);
t2 = gettime();
if (t2 - t1 > TIME_SPAN) {
vadd(&eyepos,&eyedir,&eyepos);
XClearWindow(dpy,win);
drawview(dpy,win,gc,lines,NLINES,&eyepos,&eyedir,WIDTH,HEIGHT);
t1 = gettime();
}
while (XCheckMaskEvent(dpy,-1,&ev)==True) {
switch (ev.type) {
case Expose:
while (XCheckTypedEvent(dpy,Expose,&ev));
XClearWindow(dpy,win);
drawview(dpy,win,gc,lines,NLINES,&eyepos,&eyedir,WIDTH,HEIGHT);
break;
case ButtonPress:
switch (ev.xbutton.button) {
case 3:
exit(0);
break;
}
break;
default:
break;
}
}
XFlush(dpy);
}
}
|
| コンパイル方法 |
PROMPT$ <I>gcc -I/usr/X11R6/include -o x24 x24.c vec.c -L/usr/X11R6/lib <FONT COLOR=red>\</FONT>
-lX11 -lm -lnsl -lsocket</I> <IMG SRC="/local-icons/enter.gif"> ← Solaris2.Xの豺
届淋 地模匳鱚筅苳ぢ行末の\記号は「，旅圓眤海韻ぢ行にタイプすべきである」ことを表しています。</FONT>
PROMPT$ <I>gcc -I/usr/X11R6/include -o x24 x24.c vec.c -L/usr/X11R6/lib -lX11 -lm</I> <IMG SRC="/local-icons/enter.gif">
← Linuxの豺
侑詫來髭苳侍牡ゔ 浜嘔箪跫竅讚蜒闔鶩緕鬯芍罌
|
最近の家庭用ゲーム機では、世界座標系を視野座標系へ変換する計算を ハードウェアで実行しているので、高速な３次元表示が可能となっています。 また、レンダリング（３次元の面を塗って２次元の画像を作成する） もハードウェアで行うものもあり、それらの機械では非常に高速な ３次元表示が可能です。
クリッピング (clipping) とはスクリーンからはみだす部分を「切り取る」 ことです。
ワイヤフレームにおいては、視野座標系に変換したあとで、 視野角にしたがって、スクリーンの4辺と視点を含む平面に 関するクリッピングを行います。 場合によっては、視点からあまりに遠い物体やあまりに近い 物体を排除するために、前後に2つの平面をおいてクリッピング することもあります。
x24では、線分の端点が視点よりも後方にきたときに 表示がおかしくなっていました。 視点よりも後方の点は表示しないように変更することによって 改善できます。これもクリッピングで実現できます。 表示枠をウィンドウの2/3 に設定してクリッピングする例 を以下に示します。
| clip.c |
#include "vec.h"
struct crosspoint {
int flag;
double t;
};
int clipcheck(Vector *v, double w, double h) {
int flag=0;
if (v->x < -w) flag |= 0x2;
else if (v->x > w) flag |= 0x1;
if (v->y < -h) flag |= 0x20;
else if (v->y > h) flag |= 0x10;
return(flag);
}
int clip(Vector *p, Vector *q, int w, int h, Vector *ans1, Vector *ans2) {
Vector a,b,c;
int aflag, bflag, cflag, i, j;
struct crosspoint cross[4];
double t;
a = *p; b = *q;
aflag=clipcheck(&a,w,h);
bflag=clipcheck(&b,w,h);
if ((aflag&0xf) && (aflag&0xf)==(bflag&0xf))
return(0); /* 端点がともにx軸方向にはずれている */
if ((aflag&0xf0) && (aflag&0xf0)==(bflag&0xf0))
return(0); /* 端点がともにy軸方向にはずれている */
if (!aflag && !bflag) { /* 両端点が視野内にある */
*ans1 = a; *ans2 = b;
return(1);
}
if (!bflag) { /* 端点の一方だけが視野内にあればそれを a とする */
c = a; a = b; b = c;
cflag = aflag; aflag = bflag; bflag=cflag;
}
t = b.y - a.y;
if (abs(t) > 1e-10 && (t = (h-a.y)/t) >= 0.0 && t <= 1.0) { /* y=h */
cross[3].flag=1;
cross[3].t = t;
} else cross[3].flag=0;
t = b.y - a.y;
if (abs(t) > 1e-10 && (t = (-h-a.y)/t) >= 0.0 && t <= 1.0) { /* y=-h */
cross[2].flag=1;
cross[2].t = t;
} else cross[2].flag=0;
t = b.x - a.x;
if (abs(t) > 1e-10 && (t = (w-a.x)/t) >= 0.0 && t <= 1.0) { /* x=w */
cross[1].flag=1;
cross[1].t = t;
} else cross[1].flag=0;
t = b.x - a.x;
if (abs(t) > 1e-10 && (t = (-w-a.x)/t) >= 0.0 && t <= 1.0) { /* x=-w */
cross[0].flag=1;
cross[0].t = t;
} else cross[0].flag=0;
if (!aflag) { /* 端点の一方が視野内にあれば */
t = 100000; /* large value (dummy) */
for (i=0; i<4; ++i) {
if (cross[i].flag == 0) continue;
if (cross[i].t >= 0.0 && cross[i].t < t) {
t = cross[i].t;
}
}
if (t > 1.0) {
char *p=(char *)0;
fprintf(stderr,"something bad %f",t);
*p = 0;
return(0);
}
vsub(&b,&a,&c); /* c = a + t(b-c)*/
smul(t,&c,&c);
vadd(&a,&c,&c);
*ans1 = a;
*ans2 = c;
return(1);
}
/* 両端点が視野外にある */
j = 0;
for (i=0; i<4; ++i) {
if (cross[i].flag) {
vsub(&b,&a,&c); /* c = a + t(b-c)*/
smul(t,&c,&c);
vadd(&a,&c,&c);
if (c.x <= w+1e-5 && c.x >= -(w+1e-5)
&& c.y <= h+1e-5 && c.y >= -(h+1e-5)) {
if (j==0) {
*ans1=c;
} else if (j==1) {
*ans2=c;
return(1);
}
}
}
}
return(0);
}
|
| diff -c x24.c x24a.c |
*** x24.c Mon May 22 20:01:25 2006
--- x24a.c Mon May 22 20:01:54 2006
***************
*** 63,77 ****
void drawview(Display *dpy, Window win, GC gc,
Line *lines, int n_lines,
Vector *eyepos, Vector *eyedir,
! int w, int h) {
double m[NMAT][NMAT];
! Vector p, q;
int i;
getmatrix(m,eyepos,eyedir);
for (i=0; i< n_lines; ++i) {
vmul(m,lines[i].start,&p); vmul(m,lines[i].end,&q);
project(&p,SCR_MAG/SCR_DIS,&p); project(&q,SCR_MAG/SCR_DIS,&q);
XDrawLine(dpy,win,gc,(int)p.x+w/2,(int)-p.y+h/2,(int)q.x+w/2,(int)-q.y+h/2);
}
XFlush(dpy);
--- 63,95 ----
void drawview(Display *dpy, Window win, GC gc,
Line *lines, int n_lines,
Vector *eyepos, Vector *eyedir,
! int w, int h, int sw, int sh) {
double m[NMAT][NMAT];
! Vector p, q, r;
int i;
+ {
+ int x0, y0, x1, y1;
+ x0 = (w + sw)/2; x1 = (w - sw)/2;
+ y0 = (h + sh)/2; y1 = (h - sh)/2;
+ XDrawLine(dpy,win,gc,x0,y0,x0,y1);
+ XDrawLine(dpy,win,gc,x1,y0,x1,y1);
+ XDrawLine(dpy,win,gc,x0,y0,x1,y0);
+ XDrawLine(dpy,win,gc,x0,y1,x1,y1);
+ }
getmatrix(m,eyepos,eyedir);
for (i=0; i< n_lines; ++i) {
vmul(m,lines[i].start,&p); vmul(m,lines[i].end,&q);
+ if (p.z < SCR_DIS && q.z < SCR_DIS) continue;
+ if (p.z < SCR_DIS) {r=p; p=q; q=r;} /* swap */
+ if (q.z < SCR_DIS) {
+ r.x = ((p.z-SCR_DIS) * q.x + (SCR_DIS-q.z) * p.x) / (p.z - q.z);
+ r.y = ((p.z-SCR_DIS) * q.y + (SCR_DIS-q.z) * p.y) / (p.z - q.z);
+ r.z = SCR_DIS;
+ q = r;
+ }
project(&p,SCR_MAG/SCR_DIS,&p); project(&q,SCR_MAG/SCR_DIS,&q);
+ if (clip(&p,&q,sw/2,sh/2,&p,&q)==0) continue;
XDrawLine(dpy,win,gc,(int)p.x+w/2,(int)-p.y+h/2,(int)q.x+w/2,(int)-q.y+h/2);
}
XFlush(dpy);
***************
*** 108,114 ****
if (t2 - t1 > TIME_SPAN) {
vadd(&eyepos,&eyedir,&eyepos);
XClearWindow(dpy,win);
! drawview(dpy,win,gc,lines,NLINES,&eyepos,&eyedir,WIDTH,HEIGHT);
t1 = gettime();
}
while (XCheckMaskEvent(dpy,-1,&ev)==True) {
--- 126,133 ----
if (t2 - t1 > TIME_SPAN) {
vadd(&eyepos,&eyedir,&eyepos);
XClearWindow(dpy,win);
! drawview(dpy,win,gc,lines,NLINES,&eyepos,&eyedir,WIDTH,HEIGHT,
! 2*WIDTH/3,2*HEIGHT/3);
t1 = gettime();
}
while (XCheckMaskEvent(dpy,-1,&ev)==True) {
***************
*** 116,122 ****
case Expose:
while (XCheckTypedEvent(dpy,Expose,&ev));
XClearWindow(dpy,win);
! drawview(dpy,win,gc,lines,NLINES,&eyepos,&eyedir,WIDTH,HEIGHT);
break;
case ButtonPress:
switch (ev.xbutton.button) {
--- 135,142 ----
case Expose:
while (XCheckTypedEvent(dpy,Expose,&ev));
XClearWindow(dpy,win);
! drawview(dpy,win,gc,lines,NLINES,&eyepos,&eyedir,WIDTH,HEIGHT,
! 2*WIDTH/3,2*HEIGHT/3);
break;
case ButtonPress:
switch (ev.xbutton.button) {
|
コンパイル方法
上記の例 vec.c ではいくつかの関数定義が省略されています。 省略された関数を記述し、x24 を動作させて下さい。
ただし、 void getmatrix(double m[NMAT][NMAT],Vector *v) の定義は、「視線ベクトル v を -z軸に一致させてから z軸を反転させる」4x4行列を求める関数です。
x24.c と vec.c, vec.h は http://nw.tsuda.ac.jp/admin1/c13.html からダウンロードできます。
x24a.c の内容を理解し、実際に動作させてみましょう。
x24a.c と clip.c は http://nw.tsuda.ac.jp/admin1/c13.html からダウンロードできます。
上記の Email アドレス宛に送ったメイルは http://nw.tsuda.ac.jp/cgi-bin/cgiwrap/p2r14/mailhead でヘッダ部が参照できますので、Emailを送ったあとで、 正しく提出されたかどうか必ず確認しておいて下さい。
オプション課題2ができた人は、Subject: Option 2 として課題1と 同じアドレス宛に送って下さい。
提出期限は来週木曜日の 8:50a.m. です。
