프로그래밍을 일상 생활속으로

Basis 함수의 계산 B-spline곡선을 계산하려면 먼저 basis함수를 계산해야 합니다.. B-spline basis함수의 계산은 basis함수의 정의로부터 시작합니다. B-spline basis함수의 정의는 식 )을 참조하시면 됩니다. 우리가 $N_k,p(u)$을 계산하기 위해서는 정의 상 $N_k,p-1(u)$와 $N_k+1,p-1(u)$가 필요합니다. 또 $N_k,p-1(u)$을 계산하기 위해서는 $N_k,p-2(u),N_k+1,p-2(u)$가 필요하고, $N_k+1,p-1(u)$을 계산하기 위해서는 $N_k+1,p-2(u) , N_k+2,p-2(u)$가 필요합니다. 여기서 $N_k+1,p-2(u)$가 두 번 중복됨을 주목하세요. 호출 깊이가 깊어짐에 따라서 이러한 중복되는 항의 개수가 많아지게 됩니다. 이것은 Bezier곡선의 계산에서 de asteljau 알고리즘과 비슷합니다. 조금 시각을 바꾸어서 $u$가 매듭 구간 $[u_k , u_{k+1}])$ 에 존재한다고 가정하면 이 구간에서 0이 아닌 차수가 0인 basis함수는 $N_k,0(u)$이 될 것입니다. 또 0이 아닌 차수가 1인 basis함수는 $N_{k-1},1(u) , N_k,1(u)$이 됩니다. 이렇게 해서 이 구간에서 0이 아닌 차수가 p인 basis 함수는 적어도 $p+1$개가 됩니다. $( N_k-p,p(u) , N_{k-p+1},p(u) , ... , N_{k-1},p(u) , N_k,p(u))$ 삼각형 모양의 영역에서 제일 위쪽의 화살표와 아래쪽 화살표가 가리키는 항은 바로 앞 차수의 하나의 항에서만 계산이 됩니다. 중간에 있는 부분은 정의에서처럼 앞 차수의 두 항에 의해서 계산이 이루어지게 됩니다. 전개 해보면, $$ \begin{align} N_{i,p}&=\frac{u-u_i}{u_{i+p}-u_i}N_{i,p-1}(u)+\frac{u_{i+p+1}-u}{u_{i+p+1}-u_{i+1}}N_{i+1,p-1}(u)...

Bspline 곡선의 성질 B-spline곡선은 많은 부분에서 Bezier곡선과 유사합니다. B-spline곡선은 Bezier곡선보다 더 낳은 점을 가지고 있는데, 여기서 Bspline곡선의 성질을 알아보도록 하겠습니다. 일반적인 경우로써 차수가 $p$이고 $n+1$개의 제어점을 가지고 knot vector가 $U={u_0 , u_1,...,u_m-1 , u_m}$인 Bspline곡선에 대해서 생각해 보겠습니다. Bspline곡선은 차수가 p인 여러 개의 곡선의 식으로 이루어져 있습니다. (Bezier곡선은 하나의 곡선식으로 이루어집니다.) $m=n+p+1$의 식을 만족합니다. 차수가 $p$이고 인덱스 번호가 가장 높은 basis function을 $N_{n,p}$라고 하면, 이  basis function은 매듭구간 $[u_n , u_{n+p+1})$에서 0이 아닌 값을 가집니다. 이 $N_n,p$가 가장 인덱스 번호가 높은 basis function이기 때문에 $u_{n+p+1}$가 가장 값이 큰 매듭이 됩니다. 따라서 $m=n+p+1$이 됩니다. 고정 Bspline곡선(clamped B-spline)은 양끝 제어점을 지납니다. 보다 더 엄격하게 콘벡스헐 성질을 만족시킵니다. 부분적인 편집이 가능합니다.. knot의 중복도가 k일 때 $C_{k-p}$연속성을 만족시킵니다. Bezier곡선은 B-spline곡선의 특수한 형태입니다. 어파인 변형에 대해서 불변입니다.

예를 들어가며 B-spline basis function의 형태를 살펴보도록 하겠습니다. {0 , 1 , 2 , 3}일 때 차수를 0에서 2까지 증가시키면서 basis function을 나타내었습니다. <차수가 0일 경우> 차수가 0일 때는 basis function의 정의에 의해서 step function이 됩니다. i가 0일 때는 [0,1)에서 1이 되고 나머지에서는 0이 됩니다. 1일 때는 [1,2)구간에서 1이 되고 나머지에서는 0이 됩니다. 2일 때는 [2,3)에서 1이 되고 나머지 구간에서는 0이 됩니다. <차수가 1일 경우> 차수가 0이었을 때 하나의 basis function이 유효한 구간의 크기는 1이었지만 차수가 1일 때는 구간의 크기가 2가 됩니다. $$ \begin{aligned} N_{0,1}(t)&=\frac{u-u_0}{u_1-u_0}N_{0,0}(u)+\frac{u_2-u}{u_2-u_1}N_{1,0}(u)\\ &=uN_{0,0}(u)+(2-u)N_{1,0}(u)\\ N_{1,1}(t)&=\frac{u-u_1}{u_2-u_1}N_{1,0}(u)+\frac{u_3-u}{u_3-u_2}N_{2,0}(u)\\ &=(u-1)N_{1,0}(u)+(2-u)N_{2,1}(u) \end{aligned} $$ $N_{0,1}(u)$는 $N_{0,0}(u),N_{1,0}(u)$의 합으로 구성되기 때문에 그 값이 [0,2)에서는0보다 크거나 같고 그 이외의 구간에서는 0이 됩니다. 이와 같은 이유로 해서 $N_{1,1}(u)$는 $[1,3)$에서는 0보다 크거나 같고 나머지 구간에서는 0이 됩니다. <차수가 2일 경우> $$ \begin{aligned} N_{0,2}(u)&=\frac{u-u_0}{u_2-u_0}N_{0,1}(u)+\frac{u_3-u}{u_3-u_1}(u)\\ &=0.5\times u \times N_{0,1}u + 0....

CAD쪽의 프로그래밍을 하다 보니 ENTITY들의 VOLUME을 다뤄야 할 일이 많이 생깁니다. 그래서 VOLUME에 관한 클래스를 하나 작성할려고 마음먹고 코딩에 들어갔습니다. 우선은 VOLUME은 MIN , MAX를 가지고 있으므로, private: double m_minx , m_maxx; double m_miny , m_maxy; double m_minz , m_maxz; 를 멤머 변수로 두고 기본 생성자에서 멤버 변수들을 0으로 세트했습니다. 얼핏 볼때 문제가 없었지만 정점 하나를 포함하는 VOLUME과 아무것도 포함하지 않는 VOLUME 의 구별이 되지 않는 문제점이 드러났습니다. 이것은 상당히 큰 문제점이다. CIsVolume vol; vol.Add(CIsPoint3d(100 , 100 , 100)); 와 CIsVolume vol; vol.Add(CIsPoint3d(0 , 0 , 0)); vol.Add(CIsPoint3d(100 , 100 , 100)); 이 같은 결과를 가지게 됩니다. 이러한 문제를 해결하기 위해 고민끝에 매개변수를 수정하기로 했습니다. private: double m_x , m_y , m_z; double m_width , m_height , m_depth; 를 매개 변수로 두고 기본 생성자에서 m_x , m_y , m_z는 0으로 m_width , m_height , m_depth는 -1로 세트했습니다. m_width , m_height , m_depth의 값이 모두 -1일 경우에는 VOLUME이 아무것도 포함하지 않는다는 것을 의미합니다. 이렇게 수정함으로써 위에서 불거졌던 문제점을 해결할 수 있었습니다. 첨부 파일

Bezier곡선에 유연성을 제공하기 위해서는 차수를 높이거나 분할하는 방법밖에 없었습니다. Bezier 곡선을 분할했다면 연속성을 유지하기 위해 연결되는 두 곡선 중 첫 번째 곡선의 제일 마지막 제어점에서의 기울기와 두 번째 곡선의 첫 번째 제어점에서의 기울기가 서로 같아야 했습니다. 어쨌던 차수를 높이거나 분할하는 방법은 가중 곡선의 형태를 유지하거나 계산상의 부담을 가중시키게 되는데, B-Spline 곡선에서는 차수를 높이지 않아도 $C1$연속성을 유지하기 위한 고려도 하지 않아도 됩니다. 임의의 제어점을 Bezier곡선으로 표현을 하면 차수가 제어점 개수보다 하나 작은 다항식이 생깁니다. B-Spline곡선은 Bezier곡선보다 더 낮은 차수의 식으로 곡선의 표현이 가능합니다. 낮은 차수의 식으로 곡선을 표현하려면 결과적으로 여러 개의 식이 필요하게 됩니다. 각각의 식이 곡선의 일부분을 표현하므로 곡선을 식의 개수만큼 분할하는 것과 같이 됩니다. 앞에서 우리는 Bezier곡선에 대해서 살펴보았습니다. Bezier곡선이 어떤 복잡한 모양을 띄게 되더라도 처음에는 단순한 직선에서부터 시작되었습니다. 마치 어떤 풍성한 나무라도 그것은 뿌리로부터 시작된 것 처럼. B-Spline곡선도 그것이 복잡한 모양을 띄어도 단순한 영역에서부터 시작되었습니다. 그것은 이 단순한 영역 밖에서는 존재하지 않고 오로지 그 영역 상에서만 존재합니다. 이 영역을 뿌리로 하여 곡선이 뻗어 나가게 됩니다. B-Spline곡선은 차수를 낮추면 여러 개의 식(각각의 식은B-spline곡선의 일부분을 표현한다)이 생기며 이 식들은 그것의 뿌리가 되는 영역의 일부분 상에 존재하게 됩니다. 이 영역을 여러 개의 조각으로 나누는 점들을 knot이라고 합니다. 4차의 bspline을 그리는 프로그램을 첨부 합니다.

Bspline 정의 $n + 1$개의 제어점 $(P_0 , P_1 , ... , P_{n-1} , P_n)$과 $\text{knot vector U}={U_0 , U_1 , ... , U_{m-1} , U_m}$, Bspline의 차수 p가 주어져있을 때 Bspline곡선은 $$ \begin{aligned} C(u)&=\sum_{i=0}^n N_{i,p}(u) P_i,\\ N_{i,0}&=\begin{cases} 1 & u_i \le u \lt u_{i+1}\\ 0 & otherwise \end{cases}\\ N_{i,p}&=\frac{u-u_i}{u_{i+p} - u_i} N_{i,p-1}(u) + \frac{u_{i+p+1}-u}{u_{i+p+1}-u_{i+1}} N_{i+1,p-1}(u) \end{aligned} $$ 이 됩니다. 위 식은 Bezier 곡선 식과 유사하지만 보다 많은 항들이 있습니다. $N_i,p(u)$는 Bspline의 basis function이고, 여기서 p 는 Bspline곡선의 차수이고, $P_i$는 제어점입니다. 매듭 벡터의 개수($m+1$)와 제어점의 개수와 곡선의 차수와의 관계를 살펴보면, 아래와 같은 식을 만족하게 됩니다. $$ \textcolor{red}{m=n+p+1} $$ 이 식이 성립되는 이유는 아래절에 나와 있습니다. Bspline Basis Functions Bspline의 Basis Function은 Bezier의 그것과 많은 부분에서 유사하지만 보다 복잡합니다. Bezier의 Basis Function에는 없는 두 가지의 특성이 있는데, ① 도메인이 여러 개의 knot으로 나누어져 있습니다. ② Basis Function이 도메인 전 영역에 걸쳐서 0보다 작지는 않습니다. ②번 성질에 의해서 B-spline곡선은 부분적인 편집이 가능해집니다. Bspline이 기반을 두고 있는 도메인이 여러 개의 knot으로 나누어진다고 했는데, 이...

임의의 축에 대한 회전에 대한 2번째입니다. 첫번째 보다 간단합니다. 그림에서처럼 임의의 축 $\vec{n}$에 대해서 $\vec{r}$이 가리키는 점을 $\theta$만큼 회전을 시키는 경우를 생각해봅시다. $\vec{r}$은 $\vec{n}$ 수직인 성분($\vec{r_+}$)과 평행한 성분($\vec{r_{//}}$)으로 나눌 수 있습니다. 평행한 성분은 $\vec{r}$에 대해서 회전을 한 뒤에도 그 값이 변하지 않습니다. $$ r_{//} = \big( \vec{n}\cdot\vec{r} \big) \vec{n} \\ r_+ = \vec{r} - \big( \vec{r}\cdot\vec{n} \big) \vec{n} $$ $\vec{r_+}$에 수직이고 또한 $\vec{r_{//}}$에 수직인 벡터를 $\vec{V}$라 두고, $\vec{r_+}$의 $\vec{n}$에 대한 회전은, $$ \vec{V} = \vec{n}\times\vec{r_+} = \vec{n}\times\vec{r} \\ R_{r_+} = cos(\theta)r_+ + sin(\theta)\vec{V} $$ 이 됩니다. ($r_+$를 X축, $\vec{V}$를 Y축으로 생각하시면 됩니다.) 이제 $\vec{r}$의 $\vec{n}$에 대한 회전은, $$ \begin{aligned} R_{r_+} &= R_{r_{//}} + R_{r_+} \\ &= (\vec{n}\cdot\vec{r})\vec{n} + cos(\theta)r_+ + sin(\theta)\vec{V} \\ &= cos(\theta)\vec{r} + \big( 1 - cos(\theta)\big) \vec{n}(\vec{n}\cdot\vec{r}) + sin(\theta)\vec{n}\times\vec{r} \end{aligned}$$ 이 됩니다. 단, 여기서 $\vec{n}$은 단위 벡터입니다.

임의의 축 <A>는 $X , Y ,Z$ 에 대한 요소를 가지고 있습니다. $<A>$ 의 $X,Y,Z$ 요소 중 나머지 두 요소를 제거하여 하나만 남긴다면 위에서 알아본 회전 변환에 대한 행렬식을 그대로 쓸 수가 있습니다. 그럼 문제는 어떻게 나머지 두 요소를 제거하느냐의 문제가 됩니다. 우리는 $Z$ 요소만을 남기고 나머지 두 개의 요소를 제거하도록 하겠습니다. $<A>$ 에서 $X , Y$ 요소를 제거하려면 $<A>$ 을 회전을 시켜 $Z$ 축에 일치시키면 $X ,Y$ 두 요소가 사라질 것입니다. 일단 $<A>$ 을 $Y-Z$ 평면상에 내린 후에 $Z$축과의 각을 $\alpha$ 라고 하고, $X$축을 $\alpha$ 만큼 회전을 시키면 축 <A>는 $X-Z$평면상에 놓이게 되고, 다시 여기에서 $Z$축과의 각을 $\beta$ 라고 하자. 그리고 $Y$축을 $\beta$만큼 회전을 시키면 축 <A>는 $Z$축과 동일하게 됩니다. 이제 $Z$축을 원하는 각도만큼 회전을 시킨 후에 앞의 순서를 거꾸로 하면 원래의 위치에 원하는 각도만큼 회전되어 놓이게 됩니다. 여기에서 우리가 구해야 할 변수는 $\alpha,\beta$ 입니다. 먼저 $\alpha$을 구하기 위해 <A>축을 $Y-Z$평면 상에 내린 후에, $$ d=\sqrt{(c^2_y + c^2_z)}\\ cos(\alpha)=\frac{c_z}{d},sin(\alpha)=\frac{c_y}{d} $$ 을 사용해서 $\alpha$을 구할 수가 있습니다. 여기서 $C_x,C_y,C_z$는 축 <A>의 방향 코사인입니다. $beta$는, $$ cos(\beta)=d,sin(\beta)=c_x $$ 을 사용해서 구할 수가 있습니다. 이렇게 해서 $\alpha,\beta$을 구해서 축 <A>을 $X$축에 대하여 $\alpha$만큼, $Y$축에 대하여 $beta...

두 벡터 사이의 각도는 아래의 식으로 계산이 가능합니다. $$ a = acos(\frac{\vec{A}\cdot\vec{B}} {|\vec{A}||\vec{B}|}) , (0 ≤ a ≤ 180) $$ 각도의 부호 판별 $\vec{A}$를 $\vec{Z}$에 맞추기 위해서는 a 만큼 회전을 시켜야 하고, $\vec{B}$를 $\vec{Z}$에 맞추기 위해서는 -a만큼 회전을 시켜야 합니다. 하지만 위의 공식으로는 둘다 a은 구할 수 있지만. 각도의 부호를 판별하지는 못합니다. 각도의 부호 판별은 $\vec{A}\times\vec{Z}$의 값이 양의 값이면 양의 부호를 음의 값이면 음의 부호를 붙이면 됩니다. 이 공식을 이용해 2D 평면상에서 임의의 벡터의 각도를 구해보면, X축의 각도가 $0^{\circ}$ 이므로 X축과 $\vec{A}$와의 사이각을 구합니다. 부호를 판별하기 위해 X축과 $\vec{A}$와의 외적을 구해 그 값이 음이면 앞에서 구한 사이각에 음의 부호를 붙이면 됩니다. a = acos(<X>·<A> / |X||A|) , (0 <= a <= 180) cross = <X> x <A> if cross < 0 then a = -a endif

1024개의 제어점을 가질수 있는 베지어 곡선을 그리는 프로그램입니다. 왼쪽 마우스 더블 클릭으로 베이저 곡선을 완성합니다. 베지어 곡선은 시작점과 끝점을 지나는 특성이 있습니다. 그리고 컨벡스헐 특성도 만족합니다. 첨부 파일

문자열을 구분자로 나누어서 반환값들을 받을때 C++에서는 CTokenizer라는 클래스를 만들어서 사용했었습니다. 하지만 VB에서는 그러한 함수를 기본으로 제공하고 있습니다. Dim szBuf as String Dim Tokens() As String Tokens = Split(szBuf, ":") szBuf에 들어있는 문자열을 ':' 으로 나누어서 Tokens라는 배열에 저장합니다.

코드 Dim path as String Dim szBuf as String path= App.path + "\Scales.dat" Open ScaleDataFilePath For Input As #1 Do Until EOF(1) Line Input #1, szBuf Loop Close #1

helloktk의 블로그 | ㅇ http://blog.naver.com/helloktk/80026219095 폴리곤의 내부를 겹치지 않게 분할하는 것을 폴리곤의 삼각화라고 한다.  N개의 꼭지점이 있는 폴리곤의 경우에 N-2개의 서로 겹치지 않은 삼각형을 내부에 가지게 되며, 폴리곤의 경계와 겹치지 않는  N-3개의 내부 경계라인을(diagonal)을 가지게 된다. /*Ear-cutting algorithm: not optimized, only for simple polygon, no hole **and counter clockwise ordered ploygon */ // is vertex convex or concave relative to it neighborhood??; void SetPointType(POINT P[], int Type[], int N) { for(int i=0; i<N; i++) { int iprev=(i-1+N) %N ; int inext=(i+1)%N; if(CCW(P[iprev],P[i],P[inext])>0){ Type[i]=CONVEX ; }else{ Type[i]=CONCAVE; } } }; BOOL TriangleContainsPoint(POINT P[], int TYpe[], int N, POINT A, POINT B,POINT C){ BOOL noPointInTriangle=TRUE; int i=0; while ((i < N) && (noPointInTriangle)) { if ((Type[i] ==CONCAVE)&&((A != P[i]) || (B != P[i]) ||(C != P[i]))){ int area1 = CCW(A,B,P[i]); int area2 = CCW(B,C,P[i]...

첨부파일 주어진 점들로 삼각화를 수행합니다. 최대로 허용되는 점들의 갯수는 1024개입니다.

가끔씩 프로그래밍을 하다 보면 POINT가 직선의 어느 편에 존재하는지 판단해야 할 경우가 발생합니다. 직선의 시작점에서 끝점을 바라본다고 생각하면 왼쪽에 있는 POINT는 $E\to S$와 $LHS\to S$의 외적의 값은 양의 수가 되고 오른쪽에 있는 POINT가 그 값이 음의 수가 됩니다. 당연히 0일때는 POINT가 직선상에 존재합니다.

helloktk의 블로그 | ㅇ http://blog.naver.com/helloktk/80025507906 평면상의 영역이 convex하다는 의미는 그 영역에 속하는 임의의 두점을 연결하는 선분상의 모든 점들 또한 해당영역에 속하는 경우을 의미한다. 점들의 모임에서 convex hull을 찾는 것은 점들을 잇는 선분자체가 포함되는 다각형을 찾는 것을 의미한다. 간단하게 생각할 수 있는 방법은 최외각의 한점을 기준으로해서(점들을 감싸는 최소 사각형상의 한점) 그 자신을 뺀 모든 점들이 왼편이나 일직선상에 놓일수 있는 점을 찾는다. 다시 이 찾은 점을 기준으로 나머지점들에 대해서 동일한 조건을 만족하는 점들을 차례로 찾으면, 주어진 점들을 감싸는 최소의 점들의 모임을 구할 수 있고, 이것이 convex hull을 구성한다(Gift Wrap). 이 알고리즘은 n개의 점들에 대해서 각각 O(n)정도의 찾기를 시도하므로 전체적으로 O(n^2)정도의 스텝이 필요한 알고리즘이다. 여기서 찾는 과정을 좀더 빠르게 할 수 있다면 전반적인 알고리즘의 복잡도도 감소한다.  따라서 점들은 우선 일정한 순서대로 정열을 하고난 후에 순차적으로 들어오는 점들이 왼편에 있는가만 판별하면 되는 과정으로 줄일 수 있다. 이제 conex hull을 구하는 알고리즘중에서 잘알려진 Graham Scan 알고리즘을 살펴보도록 하자. 이 알고리즘은 앞에서 설명한 과정을 그대로 따라 진행이 되는데, 우선 점들을 맨 바깥쪽에 있는 한점 (점들을 감싸는 최소 사각형상의 임의의 한점이면 충분하다. 보통은 최저의 y값을 갖는 점들중에 최대의 x값을 갖는 점으로 기준점으로  잡는다)을 기준으로 해서 각도의 크기로 점들을 정열을 해 둔상태에서 진행이 된다. 정열방법은 기준점을 각도를 계산하여 정열을 할 수 있으나, 각도수치계산의 부정확성과 복잡...

단순 폴리곤이 평면에 의해 분할이 일어난다면 폴리곤은 평면에 의해 2개로 나뉘어 집니다. 분할이 일어나는 조건은 폴리곤을 이루는 점들이 평면의 한쪽에 치우쳐 존재하지 않고 양쪽에 모두 존재해야 한다는 것입니다. 분할되는 교점은 아래 평면과 직선의 교점에서 구할 수가 있습니다. 단순 폴리곤에서 교점은 2개가 존재하게 됩니다.(intsec1 , intsec2) 2개의 폴리곤은 아래의 그림처럼 구할 수가 있습니다.(분홍색으로 이루어진 폴리곤 , 푸른색으로 이루어진 폴리곤) 이렇게 해서 단순 폴리곤의 평면에 대한 분할에 대해 간단히 알아보았습니다. CIsPoly3d* CIsPoly3d::PartionWithPlane3d(CIsPlane3d plane) { unsigned int count = 0; unsigned int edge[2] = {-1 ,}; CIsPoint3d intsec[2]; int i = 0; for(vector<CIsPoint3d>::iterator itr = m_pVertexEntry->begin();(itr + 1) != m_pVertexEntry->end() && (count < 2);itr++ , i++) { CIsPoint3d start = *itr; CIsPoint3d end = *(itr + 1); CIsPoint3d at; if(plane.FindIntersectionPoint(at , start , end)) { edge[count] = i; intsec[count++] = at; } } if(2 == count) { CIsPoint3d last; CIsPoly3d* pRet = new CIsPoly3d[2]; ////////////////////////////////////////////////////////////////////////// /// first poly3d for(i = ...

[고찰 1] S와 E는 서로 평면의 반대편에 있어야 교점이 존재하게 됩니다. 교점 C는 직선의 방정식인 $S + t*(E - S)$로 표현됩니다. 또한 C는 평면 상의 점이 되므로 $\vec{N}*C + d = 0$을 만족합니다. 첫번째 식을 두번째 식에 대입하면,$\begin{eqnarray} \vec{N}*S + t*\vec{N}*(E-S) + d = 0 \\ t = -(\vec{N}*S + d)/(\vec{N}*(E-S)) \end{eqnarray}$이 됩니다. 이렇게 해서 $t$를 구할 수 있습니다. $t$를 구한 다음 당연히 교점 C를 구할 수 있습니다.