본문 바로가기
반응형

3D Algorithm42

Morton Code 모턴 코드(Morton Code)는 3차원 또는 고차원 좌표 데이터를 1차원으로 변환하여 효율적으로 관리하기 위한 방법입니다. 이를 Z-order curve라고도 부르며, 공간 분할에서 자주 사용됩니다. Morton Code는 각 좌표의 비트를 교차(interleave)하여 1차원으로 배열합니다.각 차원의 좌표 값에서 비트를 하나씩 순서대로 꺼내어 합칩니다. 예를 들어, 3D 좌표 (x, y, z)라면, 각 차원의 비트를 교차하여 하나의 값으로 결합합니다.#include #include using namespace std;// method to seperate bits from a given integer 3 positions apartinline uint64_t splitBy3(unsigned int .. 2024. 9. 4.
CAD Revolve CAD(Computer Aided Design) 소프트웨어에는Revolve, Loft, Extrude 등 여러 가지 기능이 있습니다.이 중 Revolve는 예전 학사 때 CAD 소프트웨어를 사용하면서 제가 자주 이용했던 기능이었고 ㅎㅎ, 마침 제가 일하는 곳에서 Revolve 기능이 필요해서 이번에 한번 구현해 봤습니다. Revolve는 회전이라는 의미로 아래와 같이 중심축과 curve가 주어지면 curve를 360도 회전시켜서 3차원 모델을 생성하는 기능입니다. 기본적으로 회전 각도는 360도 회전으로 전체 형상을 생성하지만, 필요한 경우 특정 각도로 회전시켜 원하는 부분만 모델링할 때도 있습니다. 제가 구현한 것은 임의의 stl 파일이 입력으로 들어오면, stl 형상의 외곽선을 따내어 그 외곽선을 3.. 2024. 9. 3.
AABB(Axis Aligned Bounding Box) 계산과 활용 AABB 계산 기본 아이디어AABB 계산은 object를 구성하는 점들을 순회하면서 x축, y축, z축의 최대최소를 구하면 됩니다.아래와 같이 AABB가 계산되면 최소점은 (0,0,0)이고 최대점은(10,10,10)이 됩니다.  이처럼 box는 점 8개 모두 이용해서 정의해도 되지만, AABB와 같이 각축에 box가 정렬되어 있다면 대각에 해당하는 두 점으로 box를 정의할 수 있습니다. box의 중심점은 (min+max)/2가 됩니다.   어떤 형상의 특징을 파악을 위해 AABB를 사용할 수 있습니다. 만약 아래와 같이 cylinder의 AABB를 계산했다고 하면 cylinder 높이는 zmax-zmin, 직경은 ymax-ymin 또는 xmax-xmin으로 계산할 수 있습니다.  이렇게 어떤 형상이 3.. 2024. 8. 22.
임의의 점 직육면체 외부/내부 판별(Point Inside Cube) 원기둥 내부의 점 판별 코드는 아래글에서 설명했습니다. 2024.06.03 - [3D Algorithm] - 임의의 점 원기둥 내부/외부 판별 코드(c++) 임의의 점 원기둥 내부/외부 판별 코드(c++)* 아래 코드는 임의의 점이 cylinder 내부/외부에 있는지 판별하는 코드입니다. * 입력변수 설명 -  pt1: 원기둥 하단 중심점 -  pt2: 원기둥 상단 중심점 -  len: 원기둥 높이 -  radius: 원기둥 반darkrock.tistory.comCube 내부판별은 Cube가 AABB와 같이 축에 정렬이 되어 있다면 x, y, z의 min, max로 외부/내부 판별 할 수 있겠지만, OBB같이 축에 정렬이 되어 있지 않으면 내적을 이용한 정사영으로 외부/내부 판별 할 수 있습니다. AAB.. 2024. 6. 13.
PLY File Format(포맷 정보) 이전글에 stl과 obj 파일 기본정보에 대해 글을 작성 했었습니다.2023.10.23 - [3D Algorithm] - stl, obj 3D 파일 포맷 기본 정보(3D File Format) stl, obj 3D 파일 포멧 기본 정보(3D File Format)3D 파일로 주로 쓰이는 stl과 obj 파일 포맷의 기본적인 geometry 정보(에니메이션, 텍스쳐, 포인트 색상정보 제외)를 알려드리겠습니다. 이 두 파일 뿐만 아니라 대부분의 3D 파일(volume이 아닌 surface ddarkrock.tistory.com PLY 파일도 stl, obj와 같이 3d data를 저장하는 데이터 포맷입니다.PLY는 크게 두 가지 Header와 Data로 나누어서 저장합니다. * Header - 헤더 시작은 .. 2024. 6. 6.
임의의 점 원기둥 내부/외부 판별 코드(c++) * 아래 코드는 임의의 점이 cylinder 내부/외부에 있는지 판별하는 코드입니다. * 입력변수 설명 -  pt1: 원기둥 하단 중심점 -  pt2: 원기둥 상단 중심점 -  len: 원기둥 높이 -  radius: 원기둥 반지름: -  pnt: 내부/외부 판별을 위한 임의의 점struct Point{ float x; float y; float z;};bool checkInsideCylinder(Point pt1, Point pt2, float len, float radius, Point pnt){ float length_sq = len * len; float radius_sq = radius * radius; float dx, dy, dz; float pdx, pdy, pdz; float do.. 2024. 6. 3.
3차원 점 직선 투영(Point Line Projection) 방법2 3차원에서 lineP를 지나고 백터가 lineDir인 직선에 점 p를 수직으로 투영점을 구하는 두번째 방법입니다.Dist를 아래방법으로도 계산 할 수 있습니다.Dist = (P-lineP) • lineDir                      • : 내적 Dist 만큼 lineP를 이동하여 p''를 구할 수 있습니다.p'' = lineP+Dist*lineDir 참고용 방법12023.10.13 - [3D Algorithm] - 3차원 점 직선 투영(Point Line Projection) 방법1 3차원 점 직선 투영(Point Line Projection) 방법13차원에서 lineP를 지나고 백터가 lineDir인 직선에 점 p를 수직으로 투영하는 문제입니다.여러 가지 방법이 있겠지만, 간단하게 하려면 .. 2024. 5. 17.
CCW 정렬 알고리즘 이 페이지에서 설명드리는 알고리즘은 3차원에서 원형태의 point loop 순서를 ccw로 정렬하는 알고리즘입니다.point 좌표를 움직이는 것은 아니고 loop index를 ccw로 정렬하는 로직입니다. index가 ccw로 정렬이 되어 있지 않는 입력데이터를 ccw로 index를 조절한다고 보시면 될 것 같습니다. ccw 정렬 알고리즘을 위해 알아야 할 개념은 두 벡터의 사이각 계산입니다.2024.01.17 - [3D Algorithm] - 두 벡터 사이각(내적, 외적 활용) 두 벡터 사이각(내적, 외적 활용)두 벡터의 내적은 아래 식과 같이 벡터 a, b가 있을 때, 두 벡터 길이(||a||, ||b||)와 코사인 곱으로 구할 수 있습니다. 참고로 벡터 길이는 3차원을 예로 들었을 때 x제곱, y제.. 2024. 4. 23.
내적을 이용한 특징점 계산 내적은 아래 글을 통해서 두 벡터가 얼마나 비슷한 방향인가를 알 수 있고, 정사영 개념을 이용해서 벡터나 점을 투영 할 수 있다고 하였습니다. 2024.03.12 - [3D Algorithm] - 벡터 내적 외적 계산 공식과 결과 의미 벡터 내적 외적 계산 공식과 결과 의미3차원 공간의 벡터 A = (x1, x2, x3), B = (y1, y2, y3) 가 있을 때, 내적(Inner product, Dot product)은 A⋅B = x1*y1 + x2*y2 + x3*y3 으로 계산할 수 있습니다. 코사인을 이용한 내적 계산 방식은 X의 길이와 Y의 길이 곱darkrock.tistory.com2023.10.30 - [3D Algorithm] - 벡터 내적 활용(개발자 관점) 벡터 내적 활용(개발자 관점).. 2024. 4. 9.
반응형