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

프로젝트에서 사용할 어떤 대상의 Cloud 마크를 그리는 로직을 구상해 보았습니다. 제약 조건) 1. Cloud 마크 대상이 분리되어서는 안됩니다. (현재 분리된 대상의 경우 각각 Cloud 마크를 그릴 수는 있습니다.) 순서) 1. Cloud 마크 대상 획득 2. 대상 확대 3. 외곽선 구하기 4. Cloud 마크 표기 테스트 결과) 개선 사항) 1. 대상 확대 시 주위의 요소 고려 2. Cloud 마크 표기 루틴 개선 실제 적용 아래와 같은 CAD요소에 위의 로직을 적용시켜 보았습니다. Cloud 마크를 그리는 부분을 조금 개선해야겠습니다. (끝부분이 연결이 되지 않네요...)

3D 평면상의 점들을 2D로 변환하는 방법에 대해서 알아보도록 하자. 지금 개발하고 있는 2D상의 점들을 삼각화 시키는 루틴이 있는데 이 루틴을 3D 평면상의 점들에 대해서 적용시키기 위해서 3D 평면상의 점들을 2D로 변환시키는 방법이 필요하다. 고찰 1) 3D 평면을 X-Y 평면으로 맞추는 것이다. 3D 평면의 법선 벡터(n)를 Z축과 일치시키기 위해서 X,Y 축 방향으로 회전시키는 방법이다. 이 방법에 대해서는 이전 글 을 참조 하면 될것 같다. 고찰 2) 이 글에서 주로 생각해 볼것은 실제로 평면을 회전시키지 않고 2D 상으로 변환시키는 방법이다. 앞서 이야기 했듯이 이미 평면의 법선 벡터(n)를 알고 있으므로, 평면상의 임의의 점(P)을 하나 선택하고 그리고 다른 또 하나의 점을 선택한다. 그럼 하나의 벡터(u)를 구할 수 있고 이 벡터와 평면의 법선 벡터와의 외적을 통해 구한 벡터와 평면상에서 수직인 또 다른 벡터(v)를 구할 수 있다. 여기서 구한 평면상의 두 벡터(u,v)를 축으로 하여 평면상의 모든 점들을 u,v축에 대한 값으로 표현할 수 있다. 이렇게 해서 $t_2$의 값을 구할 수 있고, 마찬가지로 $t_1$의 값을 구할 수 있다. 결론적으로 모든 점들에 대하여 u,v 축에 대한 값을 구할수 있으므로 2D로 변환한 것이 된다. 고찰 2)가 고찰 1)보다 나은 점은 고찰 1)에서는 실제적으로 몇 단계의 계산을 거쳐 2D 상의 점으로 변환시킨다는 것이다. 이때 아무래도 시간과 floating point연산으로 인한 데이터 변형이 일어날수 있다는 것이다. 이에 비해 고찰 2)는 변화 루틴이 간단하다.

(1) 일반적인 타원의 방정식 = $\frac{(x - h)^2}{m} + \frac{(y - k)^2}{n} = 1$ (2) 선의 방정식 = $y = sx + t$ (2)의 식을 (1)에 대입하여 풀면 $$ x^2(n+ ms^2) + x(2sm(t-k)-2hn) + ((h^2-m)n + m(t-k)^2) = 0 $$ 이것은 2차 방정식이 된다. 이차 방정식은 근의 공식을 통하여 풀이가 가능한데.. $(n+ ms^2)$를 a로 두고 , $(2sm(t-k)-2hn)$를 b로 두고 $((h^2-m)n + m(t-k)^2$를 c로 두면 x의 값은 아래와 같이 구할 수 있다. 근의 부호 판별($sqrt(b^2 – 4ac)$)을 통하여 교차점이 두개가 있는지 혹은 하나 인지 혹은 교차하지 않는지 판별할 수 있다.

출처 What Can I Do For U? | happypcb 원문 https://blog.naver.com/happypcb/90005534378 Quaternion 개발관련/수학 2006/04/01 11:54 쿼터니언(사원수). 이 놈을 제대로 알지도 못하면서 너무 오랫동안 써왔다. 오일러각 표현 처럼 짐벌락 문제가 없기 때문에 캐릭터 애니메이션 부터 아크볼까지 많은 부분에서 사용되는 사원수. 단지 회전축과 회전량을 표현한다는 것만 알고 있었을 뿐 D3DX 에서 제공하는 함수들만 사용하면서 그냥 그런 블랙박스였다. -_-; 이렇게 원리를 모르고 사용하는 것에 대한 문제점은, 단지 정형화된 사용법에만 익숙해지고 새로운 응용법이나 약간만 꼬아놓아도 이해를 하지 못한다는 것이다. 이렇게 얇팍해서는 안된다. 최근에 이것저것 공부하면서 이제서야 사원수에 대해서 조금 알 것 같은데 간단하게 여기에다가 정리해 보도록 한다. 사원수의 연산 및 성질 등등은 인터넷이나 각종 책을 찾아보면 너무 잘 나와있으므로 생략하고, 도대체 사원수가 기하학적으로 무슨 뜻인지. 어떻게 회전이 일어나는 것인지에 대해 의미론적으로 혼자 정리해봤다. 일단 사원수는 다음과 같이 정의된다. 식(1) $$Q = q_0 + q_1*i + q_2*j + q_3*k$$ 위의 정의에서 i, j, k 는 허수이고 $q_0~q_3$ 는 실수이다. 즉, 허수부 3개와 실수부 1개로 이루어져 있다. 이것은 기하학적으로, Q가 단위 사원수 일때(Q 의 $q_0~q_3$ 으로 이루어진 벡터의 길이가 1) 다음과 같이 표현할 수 있다. 식(2) $$Q = sin(theta)*U + cos(theta)$$ 자아, 과연 식(1) 과 식(2) 모두 쿼터니언을 표현하는 거라는데 두 개가 겉보기엔 전혀 틀리구만 도대체 뭐가 같다는 걸까. 내가 헷갈렸던.. 식(2) 에서 U 는 벡터를 의미한다. 무슨 벡터인가 하면 사원수 Q로 어떤 점을 회전 변환 시킬 때 회전 축이 되는 단위...

helloktk의 블로그 | 드라곤 원문 https://blog.naver.com/helloktk/80028346861 기하 알고리즘을 특히 폴리곤알고리즘을 테스트하기 위해서는 폴리곤 데이터를 만들어야 한다. 여기서 2차원의 점들을 이용하여 간단히 simple polygon을 만드는 방법을 살펴본다. 단순폴리곤을 만들기 위해서는 점들을 정렬을 해야한다. 각각의 점들을 X축에 프로젝션을 시키면 x축에 대해서 정렬이 된다(같은 x값인경우에는 의 크기대로 정렬). 따라서 x값으로 정렬된 점들을 쭉 이어나가면 하나늬 폴리라인(poly-line)을 만들 수 있다. 그러나 원하는 폴리곤은 아니다. 이를 해결하기위해서는 점들을 직선으로 두부분으로 나누고, 직선의 윗부분은 x값이 큰순서대로 정렬을 하고, 아래 부분은 x값이 작은 순서대로 정열을 하면 폴리라인이 아닌 폴리곤을 얻을 수 있다. 직선은 어떻게 잡을까? 이것은 가장작은 x값을 갖는 점과 가장 큰 x값을 같는 점을 잇는 직선을 생각하면 편리하다. int CCW(CPoint A, CPoint B, CPoint C) { C -= B; //점B에서 C로 향하는 선분의 왼편인가, 아니면 오른편인가; A -= B; return C.x*A.y-C.y*A.x; } int comp(const void*A, const void *B) {//x->y의 크기순서대로 정렬용; int a=((POINT *)A)->x - ((POINT *)B)->x ; if(a>0) return 1 ; else if(a<0) return -1; a=((POINT *)A)->y - ((POINT *)B)->y ; if(a>0) return 1; else if(a<0) return -1; return 0; } void MakeSimplePolygon(POINT P[], i...

곡선의 변형 B-spline곡선의 변형은 아래의 조작으로 가능하다. ● 매듭 벡터의 변경 ● basis함수의 차수 변경 ● 제어점의 위치 변경 ● 중복된 제어점 사용 ● 중복된 매듭 값 사용 우리는 basis함수의 값을 계산해내는 과정을 알아보았다. 인자로 넘겨준 $u$가 속하는 매듭 구간도 구했고 거기서부터 차수를 $0$에서부터 $p$까지 증가시키면서 basis함수도 구했다. 제어점의 이동 제어점의 이동은 B-spline곡선의 모양을 변형하는 한 방법이 된다. 제어점 $P_k$을 이동시키면 B-spline곡선 $C(u)$중 매듭 구간 $[U_k,U_{k+1})$에 속하는 부분만 변형이 된다. (나머지 구간에서의 B-spline곡선은 0이 되기 때문에 이동에 의한 변형은 생기지 않는다.) 조금 더 자세히 살펴보자면 제어점이 이동되어지는 벡터의 방향으로 곡선이 변형이 된다. $P_k$가 새로운 위치 $P_{k+v}$로 이동되었다면, 이 된다. 기존의 곡선에서 $N_k,p(u)v$만큼 이동된다는 것을 알 수 있다. 하지만 여기서 $u$가 매듭 구간 $[U_k,U_{k+1})$에 속하지 않는다면 곡선의 변형은 없을 것이다.

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으로 나누어진다고 했는데, 이...

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

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

단순 폴리곤이 평면에 의해 분할이 일어난다면 폴리곤은 평면에 의해 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 = ...

helloktk의 블로그 | ㅇ http://blog.naver.com/helloktk/80025637242 주어진 단순폴리곤이 convex인지 concave 인지는 이웃하는 변끼리의 cross 가 모두 같은 부호를 갖는지를 체크하면 된다. 중간에 부호가 바뀌면 해당 폴리곤의 concave이다. 이웃하는 세꼭지점이 일직선상에 놓인 경우는 제외해야 한다. 폴리곤이 simple인지 아닌지는 어떻게 판별할까? /*주어진 심플한 다각형이 convex인지 concave인지를 판별한다. 점들이 일직선상에 놓인 상황에 있으면 0을 리턴한다. */ int is_convex_polygon(POINT p[], int N) { int i; int flag = 0; if (N < 3) return(0); for (i=0; i<N; i++) { int j = (i + 1) % N; int k = (i + 2) % N; double z = (p[j].x - p[i].x) * (p[k].y - p[j].y); z -= (p[j].y - p[i].y) * (p[k].x - p[j].x); if (z < 0) flag |= 1; else if (z > 0) flag |= 2; if (flag == 3) return (CONCAVE); } if (flag != 0) return (CONVEX); else return (0); }

picbuddy님의 블로그(Mesh Generation) | 서캐 http://blog.naver.com/picbuddy/80021589591 Determining whether or not a polygon (2D) has its vertices ordered clockwise or counterclockwise Written by Paul Bourke March 1998 The following describes a method for determining whether or not a polygon has its vertices ordered clockwise or anticlockwise for both convex and concave polygons. A polygon will be assumed to be described by N vertices, ordered $$ (x_0,y_0),(x_1,y_1),(x_2,y_2),...(x_{n-1},y_{n-1}) $$ A simple test of vertex ordering for convex polygons is based on considerations of the cross product between adjacent edges. If the crossproduct is positive then it rises above the plane (z axis up out of the plane) and if negative then the cross product is into the plane. $$ \begin{aligned} cross product &= ((x_i - x_{i-1}),(y_i - y_{i-1})) \times ((x_{i+1} - x_i),(y_{i+1} - y_i))\\ &= (x_i - x_{i-1}) * (y_{i+1} - y_i) - (y_i - y_{i-1}) * (x_{i+1} - x_i) \en...