본문 바로가기

computer science7

Karatsuba Multiplication 1. 문제 정의 입력 : 두개의 n자리 양수 x, y 출력 : x y 의 곱 2. Grade-School Algorithm 5678 * 1234 계산 시 다음과 같이 계산 5678 * 4 + (5678 * 3) * 10 + (5678 * 2) * 100 + (5678 * 1) * 1000 복잡도는 O(n²) -> 너무 느리다 3. Improving 3.1. Divide and conquer Divide and conquer란? 큰 문제를 더 작고 쉬운 문제들의 모음으로 쪼개어 풀어내는 것 3.2. Integer Multiplication에 적용 1234 = 12 * 100 + 34 1234 * 5678 = (12 * 100 + 34) (56 * 100 + 78) = (12 * 56)10000 + (34 .. 2021. 9. 8.
고정 소수점과 부동 소수점 고정 소수점과 부동 소수점은 컴퓨터에서 실수(real number)를 표현하는 방법이다 1. 고정 소수점 (Fixed Point) 말 그대로 소수점이 고정된 형태이다. 32비트의 수라면 언제나 1비트를 부호 표현에, 15비트를 정수 표현에, 16비트를 소수 표현에 사용하는 식이다. 소수부에 할당된 비트의 숫자에 따라 정밀도가 달라진다. 예를 들어 부호부에 1개의 비트, 정수부에 n개의 비트, 소수부에 m개의 비트를 할당한 수의 경우, 1. 표현 가능한 실수는 2^(n+m+1)개이다. 2. 표현 가능한 가장 작은 차이는 2^(-m)이 되며 이를 분해능이라고 한다. 표현 가능한 실수의 범위와 정밀도가 제한적이기 때문에 실질적으로 잘 사용하지 않는다. 2. 부동 소수점 (Floating Point) 부동의 부.. 2021. 7. 26.
왜 정규화 벡터를 사용하는가 정규화 벡터를 사용하는 이유 http://stackoverflow.com/questions/10002918/what-is-the-need-for-normalizing-a-vector http://stackoverflow.com/questions/2304634/why-do-we-need-a-unit-vector-in-other-words-why-do-we-need-to-normalize-vector - 필수적으로 정규화 벡터를 사용할 필요는 없다. 그러나 정규화 벡터는 식을 굉장히 축소시켜주고, 따라서 API 또한 매우 간단해진다. 만약 u,v 두 벡터의 각도를 구한다고 생각해보자. 만약 두 벡터가 크기가 1인 unit 벡터라고 하면, 둘을 그냥 arccos(u*v)를 취하면 된다. 그러나 두 벡터가 un.. 2021. 7. 26.
OBB (Oriented Bounding Box)와 AABB (Axis-Aligned Bounding Box) 개요 -OBB와 AABB? 1. Bounding Box 3D world에서 교차 검사는 매우 중요한 이슈이다. 게임을 예로 들자면, 캐릭터끼리 충돌 검출도 해야하고 마우스 picking도 해야되고 타격 판정도 해야되기 때문이다. 그래서 캐릭터 모델(메쉬) 나 특정 범위, 지형 구조물 등에 충돌 판정을 위한 박스나 단순한 모양의 bounding volume을 씌운다. 그렇게 해서 복잡한 메쉬끼리 교차 검사를 하는 것이 아니라 단순한 volume들 끼리 교차 검사를 하는 것이다. 만약 메쉬를 이루는 모든 삼각형끼리 충돌 검사를 한다면 너무 비용이 커질 것이다. 가장 많이 쓰이는 모양이 box인데, 이 box에는 2종류의 타입이 있으니 그것이 바로 aabb와 obb이다. 2. AABB AABB는 Axis-Al.. 2021. 7. 26.
동족좌표계와 동차좌표 (Affine Space, Homogeneous coordinate) 개요 동족좌표계? Affine Space? 동차좌표? Homogeneous coordinate? 왜 1,4 행렬로 3차원상의 점과 벡터를 표현하나요? 1. Affine Space(동족 좌표계)란? 어파인(혹은 어핀) 스페이스는 다른 말로 동족 좌표계 라고도 하며, 쉽게 말하면 벡터와 점을 같은 것으로 간주하는 공간이다. 3차원 공간에 (1,2,3)로 표현되는 무언가가 존재한다면, 이것은 1,2,3 위치의 점이라고 말할 수도 있고, 원점에서부터 1,2,3으로 향하는 벡터라고도 볼 수 있는 것이다. 이렇게 점과 벡터를 함께 표현하게 되면, 점과 점의 뺄셈으로 벡터를 얻을 수도 있고, 점에 벡터를 더해 다른 위치의 점을 구할 수도 있다. 그러나 그냥 똑같이 표현하면 이게 점인지 벡터인지 알 수가 없기 때문에 .. 2021. 7. 26.
컴퓨터 그래픽스 렌더링 파이프라인의 개요 1. 렌더링이란? 컴퓨터로 모델 혹은 씬으로부터 영상을 만들어내는 모든 과정 (출처 - wiki(http://ko.wikipedia.org/wiki/%EB%A0%8C%EB%8D%94%EB%A7%81)) 컴퓨터에 존재하는 모델, 혹은 씬을 구성하는 수치들로부터 모니터 혹은 영상을 어떻게 나타낼 것인가에 대한 문제이다. 2. 렌더링 파이프라인이란? 렌더링 파이프라인이란 3차원 이미지(모델 혹은 모델로 구성된 씬)로부터 2차원 래스터 이미지를 표현하는 것이라고 할 수 있다. 우리는 모니터에 점과 선뿐만 아니라 면도 표현해야하기때문에 거의 모든 모니터 혹은 영상 기기가 벡터가 아닌 래스터 디스플레이를 채용하고 있다. 벡터와 래스터 디스플레이의 차이 래스터 디스플레이 벡터 디스플레이 3. 렌더링 파이프라인의 구성.. 2021. 7. 26.
반응형

티스토리툴바