A Fast Slicing Algorithm of the 3D-Scanned Point Clouds Object for Rapid Prototyping

Abstract

역공학(Reverse Engineering)과 쾌속 조형(Rapid Prototyp-ing, 3D Printing) 기술은 설계 및 생산 분야의 산업 전반에 큰 변화를 불러왔다. 역공학을 수행하기 위해서는 3차원 스캐닝 작업에서 얻는 점군 데이터에 포함된 불확정성을 제거하고 데이터를 변환하는 작업이 선행되어야 하는데, 이를 위해서 표면 모델로의 변환이 일반적이었다. 마찬가지로, 기존에는 3차원 스캔된 물체의 점군 데이터를 쾌속 조형하기 위해, 단면 정보를 계산하는 슬라이싱(Slicing) 작업에 앞서 점군을 표면 모델로 변환하는 표면 재구성(Surface Reconstruction) 작업이 선행되어야 했다. 하지만 이러한 변환 작업은 선행 과정임에도 불구하고 많은 수동적인 연산을 필요로 하고, 변환된 이후에도 표면 모델의 오류를 교정하는 메쉬 복원(Mesh Healing) 작업을 수반하므로 매우 비효율적이다. 따라서, 본 논문에서는 표면 모델로의 변환을 거치지 않고 점군 데이터를 곧바로 슬라이싱 하는 알고리즘을 제안한다. 제안된 알고리즘은 점군 데이터를 입력 받은 뒤, 광선과 모델의 교차점으로써 형상을 묘사하는 2.5차원 광선 표현(R-Rep.) 모델로 이를 변환한다. 먼저, 점군 데이터로부터 이동 최소 자승(Moving Least Square, MLS) 표면을 정의하고 각 광선의 최근접 k 이웃(k-Nearest Neighbors)을 광선 위에 투사함으로써 교차점을 찾을 확률이 높은 쿼리(Query) 지점을 얻는다. 이후 각 쿼리에서 MLS값을 계산하여 가위치법(Regula-Falsi Method)을 이용해 값의 부호가 서로 다른 연속된 두 쿼리 사이에서 수치해석적으로 교차점을 찾음으로써 광선 표현 모델을 얻는다. 제안된 알고리즘에서는 표면 재구성 및 복원 작업을 거치지 않고 점군 데이터를 광선 표현 모델로 곧바로 변환한다. 또한, 각 광선에서 감기 횟수 규칙(Non-zero Winding Rule)과 홀-짝 규칙(Even-Odd Rule)을 이용해 모델의 내·외부를 판별하여 최종적으로 흑백 이미지 형식의 단면 정보를 출력할 수 있었다. 결과적으로, 기존의 과정에서 표면 모델로의 변환 과정을 생략하고 곧바로 점군 데이터를 광선 표현 모델로 변환함으로써 빠르고 효율적으로 점군 모델을 쾌속 조형할 수 있음을 보였다.

Reverse Engineering(RP) technology and Rapid Prototyping technology have brought a great change in the field of design and production industries. For the Reverse Engineering, it is necessary to remove the uncertainty lies in the 3D-scanned point clouds data. In general, the conversion into a surface model is adopted to represent the scanned data. In the same manner, in order to prototype point clouds, the Surface Reconstruction process must be performed first and then the Slicing operation follows. However, this conventional workflow is inefficient because it requires too much manually operated computations in the preprocessing step. Even after the conversion, additional Mesh Healing operations must be conducted to correct non-manifoldness in the converted surface model. Thus, in this paper, we propose a fast slicing algorithm to calculate the layer-by-layer cross-sections of point clouds for RP process. The proposed algorithm adopts a 2.5-dimensional Ray-Representation(R-Rep.) model to slice the object, which stores the information of intersections between rays and the model. First, we define the Moving Least Square (MLS) Surface from the points and search for k-Nearest Neighbors of each ray to project them on the ray. The projected points become Query Points with high probabilities that an intersection exists around them. Then, the MLS value computed at each query is used to the Regula-Falsi method to find the intersections between two consecutive queries with opposite signs. In the proposed algorithm, the input data is directly converted into the R-Rep. model without surface reconstruction process or mesh restoration process. In addition, the errors in the model geometry can be quickly detected and corrected by examining the Non-Zero Winding Rule from each ray. Finally, we can directly obtain black/white cross-sectional images from determining the inside/outside of the model using the Even-Odd Rule from all rays. As a result, it shows that the point clouds can be efficiently prototyped by converting them directly into the R-Rep. model, instead of the surface model.