200912799 九、發明說明： 【發明所屬之技術領域】 本發明涉及一種距離計算系統及方法。 【先前技術】 近年來，隨著電腦硬體性能的提高及價格的降低，其 在量測系統中被大量的引入。做法一般是使用點雲獲取裝 置獲取物體的點雲（即由多個三維離散點組成的點的集 合），而後將點雲資料登錄電腦，執行相應軟體對點雲資料 進行各種處理，比如最優匹配、碰撞檢測、逆向工程等。 在對點雲的各種處理中，經常要進行距離計算，如計 算點雲到點雲的最近距離。傳統的計算最近距離的方法通 常是計算一個點雲中的所有點與另一個點雲中的所有點的 距離，從中找到最近距離。而點雲資料一般密度較大，通 常有數十萬、上百萬、甚至上千萬，因此，按照傳統的方 法計算點雲到點雲的最近距離需要很大的計算量，導致運 算速度緩慢。 ' 因此，需要一種距離計算系統及方法，能夠快速方便 地計算點雲到點雲的最近距離。 【發明内容】 鑒於以上内容，有必要提供一種點雲到點雲的最近距 離計算系統及方法，其可快速地計算雜亂點雲到雜亂點雲 的最近距離。 一種點雲到點雲的最近距離計算系統，該系統包括電 腦及儲存單元。所述電腦包括：接收模組，用於從所述儲 6 200912799 2早:::收點雲資料’所述點雲資料包括 及-組參考點雲；包圍盒構造模組，用於 =造包圍盒；選擇模組，用於遍層 二相 切擇-個未進行過距離計算的點;及最近::二二 述選擇的點最近的奸個單 *找距離上 若干個單元包園人 圍是，透過計算該點與該 雲的最近距離，㈣’得到該點到參考點 近點。 A該取近距離所對應的參考點雲中的最 雲：:;離計算方法’該方法包括： 移動點雲中：=:考:::造包圍盒;⑷ ⑷根據上述料2=；：個未4行過距離計算的點； 干個單元包圍盒，透過計算該點與該若干 最近距離二及的距離’得到該點到參考點雲的 點;及_驟;:= 的最近 都進行過轉計算。 ㈣移動點#中的所有點 距離知技術’本發明所提供的點雲到點雲的最近 雲到點雲的最^方法’採用了構造包圍盒的方法，計算點 速度。农 距離，極大地減少了計算量，提高了運行 【實施方式】 200912799 參閱圖1所示，3 系統較佳實η , &發明點雲到點雲的最近距離計算 腦，該電腦包括Ϊ硬體架構圖。該系統主要包括—台電 機2連接有铸存單頁元7^1、主機2、鍵盤3及滑鼠4。所述主 算點= 可以用於儲存多組點雲資料以及在計 所述主機 收點雲資料，用於從儲存單元5中接 最近距離。接㈣點雲資料，計算點雲到點雲的 面，所述主機2,用於提則戶圖形介 像，並可以時時主機2接㈣點雲資料所組成的圖 亏吋顯不對點雲的處理結果。 所述鍵盤3及、、發9 連接於主機2,主要用作在 右的取相離時的輪人、輪㈣備。 如圖2所示，县闰16匕_ 機2主要包括接收的功能模組圖。所述主 22、最近轉^選擇模組 發明所稱賴岐及_模組25。本 争虺人h 凡成—特疋功能的電腦程式段，比铲+ =:::=:執一此在二 雲資=====如接收點 點雲可以稱為參考^組點雲可⑽為移動點雲，另-组 8 200912799 所述包圍盒構造模組21用於為參考點雲構造包圍 盒。為參考點雲構造包圍盒是為了將參考點雲中的所有點 建立起關聯。所述包圍盒構造模組21透過如下步驟構造包 圍盒：根據參考點雲中各點的三維座標值，找到該參考點 雲中座標最小的點的三維座標值及座標最大的點的三維座 標值；根據上述兩組三維座標值，將其中的X、Y、Z座標 值進行組合，得到8組三維座標值；以得到的8組三維座標 值為頂點，構造所述參考點雲的包圍盒；以一個網格間距 將上述包圍盒劃分為多個單元包圍盒；為每個單元包圍盒 設置標號。 所述選擇模組22主要用於遍曆移動點雲中的點，從中 選擇一個未進行過距離計算的點。 所述最近距離計算模組23用於根據上述對參考點雲 構造的包圍盒，尋找距離上述選擇的點（下稱：該點）最 近的若干個單元包圍盒，透過計算該點與該若干個單元包 圍盒中的所有點的距離，得到該點到參考點雲的最近距 離，以及該最近距離所對應的參考點雲中的最近點。 所述儲存模組24用於儲存上述得到的最近距離及最 近點。 所述判斷模組25主要用於遍曆移動點雲中的所有 點，判斷該移動點雲中是否還有未進行過距離計算的點。 若有，則所述選擇模組22選擇移動點雲中的下一點。否則， 點雲到點雲的最近距離計算完畢。 參閱圖3所示，是本發明第一較佳實施例點雲到點雲 9 200912799 的最近距離計算方法較佳實施例的實施流程圖。 步驟S10，接收模組20從儲存單元5中接收點雲資料。 本實施例中，接收模組20從所述儲存單元5中接收兩組點雲 資料，其中一組點雲可以稱為移動點雲，另一組點雲可以 稱為參考點雲。 步驟S11，包圍盒構造模組21為參考點雲構造包圍 盒。為參考點雲構造包圍盒是為了將參考點雲中的所有點 建立起關聯。構造包圍盒的詳細步驟請參閱圖4所示。 步驟S12，選擇模組22遍曆移動點雲中的點，從中選 擇一個未進行過距離計算的點。 步驟S13，最近距離計算模組23根據上述對參考點雲 構造的包圍盒，尋找距離上述選擇的點（下稱：該點）最 近的若干個單元包圍盒，透過計算該點與該若干個單元包 圍盒中的所有點的距離，得到該點到參考點雲的最近距 離，以及該最近距離所對應的參考點雲中的最近點。計算 最近距離的詳細步驟請參閱圖5所示。 步驟S14，儲存模組24儲存上述得到的最近距離及最 近點。 步驟S15，判斷模組25遍曆移動點雲中的點，判斷該 移動點雲中是否還有點沒有被選擇過，即判斷該移動點雲 中是否還有未進行過距離計算的點。若有，則返回步驟 S12，所述選擇模組22從移動點雲中選擇下一個未進行過 距離計算的點。否則，點雲到點雲的最近距離計算的流程 執行完畢。 200912799 圖4是圖3中步驟S11對參考點雲構造包圍盒的具體流 程圖。 步驟S110，所述包圍盒構造模組21根據參考點雲中各 ' 點的三維座標值，找到該參考點雲中座標最小的點的三維 座標值（ptMin[0]，ptMin[l]，ptMin[2])及座標最大的點 的三維座標值（ptMax[0] ’ ptMax[l] ’ ptMax[2])。 步驟Sill，所述包圍盒構造模組21將上述兩組三維座 標值中的X、Y、Z座標值進行組合，得到8組三維座標值， 分別為（ptMin[0]，ptMin[l]，ptMin[2] )、（ ptMin[0]， ptMin[l]，ptMax[2])、（ptMin[0]，ptMax[l]，ptMin[2])、 (ptMin[0]，ptMax[l]，ptMax[2] )、（ ptMax[0]，ptMax[l]， ptMax[2] )、（ ptMax[0]，ptMax[l]，ptMin[2] )、（ ptMax[0]， ptMin[l] ’ ptMax[2])及（ptMax[0] ’ ptMin[l] ’ ptMin[2])。 步驟S112，所述包圍盒構造模組21以上述8組三維座 標值為頂點，構造所述參考點雲的包圍盒。 , 步驟S113，所述包圍盒構造模組21以一個網格間距 \200912799 IX. Description of the Invention: [Technical Field of the Invention] The present invention relates to a distance calculation system and method. [Prior Art] In recent years, with the improvement of computer hardware performance and price reduction, it has been introduced in a large number in measurement systems. The method generally uses a point cloud acquisition device to acquire a point cloud of an object (ie, a set of points consisting of a plurality of three-dimensional discrete points), and then log the point cloud data to the computer, and execute corresponding software to perform various processing on the point cloud data, such as an optimal Matching, collision detection, reverse engineering, etc. In various processes of point clouds, distance calculations are often performed, such as calculating the closest distance from a point cloud to a point cloud. The traditional method of calculating the nearest distance is usually to calculate the distance between all points in one point cloud and all points in another point cloud, and find the closest distance. Point cloud data is generally dense, usually hundreds of thousands, millions, or even tens of millions. Therefore, calculating the nearest distance from point cloud to point cloud according to the traditional method requires a large amount of calculation, resulting in slow operation. . Therefore, there is a need for a distance calculation system and method that can quickly and easily calculate the closest distance from a point cloud to a point cloud. SUMMARY OF THE INVENTION In view of the above, it is necessary to provide a point cloud to point cloud nearest distance calculation system and method that can quickly calculate the closest distance from a chaotic point cloud to a clutter point cloud. A point cloud to point cloud nearest distance computing system that includes a computer and a storage unit. The computer includes: a receiving module, configured to receive cloud data from the storage 6 200912799 2 early::: the point cloud data includes and a group reference point cloud; a bounding box structure module, for making Bounding box; selection module, used for merging two-phase cutting - a point that has not been calculated by distance; and most recently:: two or two selected points of recent singularity * finding a number of units in the distance Around, by calculating the closest distance of the point to the cloud, (4) 'get the point to the reference point near point. A should take the closest cloud to the most cloud in the reference point cloud::; from the calculation method' The method includes: moving the point cloud: =: test::: building a bounding box; (4) (4) according to the above material 2 =;: a point that does not have a distance calculation of 4 lines; a unit bounding box, the distance from the point to the reference point cloud is calculated by calculating the distance between the point and the several nearest distances; and _c ; Overturn calculation. (4) All points in the moving point # Distance technology The closest method of the point cloud to the point cloud provided by the present invention is the method of constructing a bounding box to calculate the point velocity. Agricultural distance, greatly reduced the amount of calculation, improved the operation [Implementation] 200912799 See Figure 1, 3 system is better η, &invention; point cloud to point cloud nearest distance calculation brain, the computer includes Ϊ hard Body diagram. The system mainly includes a machine 2 connected with a cast single page 7^1, a host 2, a keyboard 3 and a mouse 4. The main point = can be used to store a plurality of sets of point cloud data and count the cloud data of the host point for receiving the closest distance from the storage unit 5. Connect (4) point cloud data, calculate the point cloud to the point cloud surface, the host 2, for drawing the graphical user interface, and sometimes the host 2 connected (four) point cloud data composed of the map is not right point cloud Processing results. The keyboard 3 and the hairpin 9 are connected to the main body 2, and are mainly used as a wheel person or a wheel (four) in the case of taking the right side. As shown in Figure 2, the county 闰 16 匕 machine 2 mainly includes the received functional module diagram. The main 22, the recent switch selection module is claimed to be the Lai and the _ module 25. This contender h is a computer program segment of the special function, than the shovel + =:::=: one in the second cloud ===== If you receive the point cloud can be called the reference ^ group point cloud (10) is a moving point cloud, and the bounding box construction module 21 of the other group 8 200912799 is used to construct a bounding box for the reference point cloud. The bounding box is constructed for reference point clouds in order to correlate all points in the reference point cloud. The bounding box structure module 21 constructs a bounding box by searching: according to the three-dimensional coordinate value of each point in the reference point cloud, finding the three-dimensional coordinate value of the point with the smallest coordinate in the reference point cloud and the three-dimensional coordinate value of the point with the largest coordinate According to the above two sets of three-dimensional coordinate values, the X, Y, and Z coordinate values are combined to obtain eight sets of three-dimensional coordinate values; and the obtained three sets of three-dimensional coordinate values are vertices, and the bounding box of the reference point cloud is constructed; The above bounding box is divided into a plurality of unit bounding boxes at a grid spacing; labels are set for each unit bounding box. The selection module 22 is mainly used to traverse the points in the moving point cloud, and select a point from which the distance calculation has not been performed. The nearest distance calculation module 23 is configured to search for a plurality of unit bounding boxes that are closest to the selected point (hereinafter referred to as the point) according to the bounding box constructed for the reference point cloud, and calculate the point and the plurality of units The unit surrounds the distance of all the points in the box, and gets the closest distance from the point to the reference point cloud, and the closest point in the reference point cloud corresponding to the closest distance. The storage module 24 is configured to store the closest distance and the closest point obtained above. The determining module 25 is mainly used to traverse all points in the moving point cloud, and determine whether there are any points in the moving point cloud that have not been subjected to distance calculation. If so, the selection module 22 selects the next point in the moving point cloud. Otherwise, the closest distance from the point cloud to the point cloud is calculated. Referring to FIG. 3, it is a flowchart of an implementation of a preferred embodiment of a nearest distance calculation method of a point cloud to point cloud 9 200912799 according to a first preferred embodiment of the present invention. In step S10, the receiving module 20 receives the point cloud data from the storage unit 5. In this embodiment, the receiving module 20 receives two sets of point cloud data from the storage unit 5, wherein one set of point clouds may be referred to as a moving point cloud, and another set of point clouds may be referred to as a reference point cloud. In step S11, the bounding box structure module 21 is a reference point cloud structure bounding box. The bounding box is constructed for reference point clouds in order to correlate all points in the reference point cloud. See Figure 4 for the detailed steps to construct the bounding box. In step S12, the selection module 22 traverses the points in the moving point cloud, and selects a point from which the distance calculation has not been performed. Step S13, the nearest distance calculation module 23 searches for a plurality of unit bounding boxes that are closest to the selected point (hereinafter referred to as the point) according to the bounding box constructed for the reference point cloud, and calculates the point and the plurality of units by calculating the point The distance from all points in the bounding box, the closest distance from the point to the reference point cloud, and the closest point in the reference point cloud corresponding to the closest distance. See Figure 5 for detailed steps to calculate the closest distance. In step S14, the storage module 24 stores the closest distance and the closest point obtained as described above. In step S15, the determining module 25 traverses the point in the moving point cloud, and determines whether there is still a point in the moving point cloud that has not been selected, that is, whether there is a point in the moving point cloud that has not been subjected to distance calculation. If so, the process returns to step S12, and the selection module 22 selects the next point from the moving point cloud that has not been subjected to the distance calculation. Otherwise, the process of calculating the nearest distance from the point cloud to the point cloud is completed. 200912799 Fig. 4 is a specific flow chart of the reference point cloud construction bounding box in step S11 of Fig. 3. Step S110, the bounding box construction module 21 finds the three-dimensional coordinate value of the point with the smallest coordinate in the reference point cloud according to the three-dimensional coordinate value of each point in the reference point cloud (ptMin[0], ptMin[l], ptMin [2]) and the three-dimensional coordinate value of the point with the largest coordinate (ptMax[0] ' ptMax[l] ' ptMax[2]). In step Sill, the bounding box structure module 21 combines the X, Y, and Z coordinate values of the two sets of three-dimensional coordinate values to obtain eight sets of three-dimensional coordinate values, which are respectively (ptMin[0], ptMin[l], ptMin[2] ), ( ptMin[0], ptMin[l], ptMax[2]), (ptMin[0], ptMax[l], ptMin[2]), (ptMin[0], ptMax[l] , ptMax[2] ), ( ptMax[0], ptMax[l], ptMax[2] ), ( ptMax[0], ptMax[l], ptMin[2] ), ( ptMax[0], ptMin[l ] ' ptMax[2]) and (ptMax[0] ' ptMin[l] ' ptMin[2]). In step S112, the bounding box structure module 21 constructs a bounding box of the reference point cloud by using the above-mentioned eight sets of three-dimensional coordinate values as vertices. Step S113, the bounding box construction module 21 has a grid spacing.
Step將上述包圍盒劃分為多個單元包圍盒，該網格間距 Step根據用戶的需求可以取不同的值，若用戶希望每個單 元包圍盒内的點多些，則可以將Step的值設置的大一些， 否則，若用戶希望每個單元包圍盒内的點少些，則可以將 Step的值設置的小一些。 步驟S114，所述包圍盒構造模組21為每個單元包圍盒 設置標號。 參閱圖5所示，是圖3中步驟S13計算一點到參考點雲 11 200912799 隶近距離的具體流程圖。 步驟S130，所述最近距離計算模組23透過將所選擇的 點（該點）向參考點雲包圍盒投影，得到距離該點最近的 單元包圍盒，並計算該點距離該單元包圍盒的距離D。 步驟S131，所述最近距離計算模組23以該點為中心， 以2 (D+n*Step)為邊長，構造一個立方體區域，使該立 方體區域與參考點雲包圍盒相交，得到一個相交區域。其 中，η為構造立方體區域的次數，此時n=l ; Step為參考點 雲單元包圍盒的邊長。 步驟S132，所述最近距離計算模組23得到該相交區域 的起始位置與終止位置的單元包圍盒標號，並得到該相交 區域的單元包圍盒數量。 步驟S133，所述判斷模組25遍曆該相交區域内的所有 單元包圍盒，判斷該所有單元包圍盒内是否有參考點雲中 的點。 若該所有單元包圍盒内沒有參考點雲中的點，則返回 步驟S131，所述最近距離計算模組23以該點為中心，以2 (D+n*Step)為邊長，構造一個立方體區域，得到一個相 交區域。此時，n=2。若相交區域内的單元包圍盒中還是 沒有參考點雲的點，則繼續構造立方體區域，其中的η依次 遞增。 若單元包圍盒内有參考點雲的點，則在步驟S134中， 所述最近距離計算模組23計算該所有單元包圍盒内的所有 點到該點的距離，並得到其中的最近距離d。 12 200912799 步驟S135，判斷模組25判斷是否心（D+n*Step)。 純（D+n*SteP)，則步驟叫2中，破定該距離d為該 點到參考點雲的最近距離。 否則’若d> (D+n*Step)’該轉坏―定是該點到灸 考點雲的最近距離’則在步驟S136中，儲存模組24暫存該 距離d，記作dmin。 〆 執行上述描述的步驟S131及步驟Sl32，得到一個更大 的相交區域。 」步卿37,所述最近距料算模㈣將本謂到的相 父區域減去上次得到的相交區域。 步驟S138，判斷模組25遍曆上述相減後得到的相交區 域中的所有單元包圍盒，判斷該所有單元包圍盒内是 在參考點雲的點。 若沒有參考點雲的點，則重複執行上述步卿31、步 驟幻32、步驟S137及步驟S138。 乂 X 若在步驟S138中，判斷該單元包圍盒内存在參考點带Step divides the bounding box into a plurality of unit bounding boxes, and the grid spacing step can take different values according to user requirements. If the user wants each unit to surround more points in the box, the Step value can be set. Larger, otherwise, if the user wants fewer points in each unit to surround the box, you can set the value of Step to be smaller. In step S114, the bounding box construction module 21 sets a label for each unit bounding box. Referring to FIG. 5, it is a specific flowchart of calculating the point distance to the reference point cloud 11 200912799 in step S13 in FIG. Step S130, the nearest distance calculation module 23 projects the selected point (the point) to the reference point cloud bounding box to obtain the unit bounding box closest to the point, and calculates the distance of the point from the unit bounding box. D. Step S131, the nearest distance calculation module 23 centers on the point and constructs a cube area with 2 (D+n*Step) as a side length, so that the cube area intersects with the reference point cloud bounding box to obtain an intersection. region. Where η is the number of times the cube region is constructed, at this time n=l; Step is the side length of the reference point cloud unit bounding box. In step S132, the nearest distance calculation module 23 obtains the unit bounding box number of the starting position and the ending position of the intersecting area, and obtains the number of unit bounding boxes of the intersecting area. In step S133, the determining module 25 traverses all the cell bounding boxes in the intersecting area, and determines whether all the cells in the bounding box have points in the reference point cloud. If there is no point in the reference point cloud in all the cell bounding boxes, then returning to step S131, the nearest distance calculating module 23 constructs a cube centering on the point and using 2 (D+n*Step) as the side length. Area, get an intersection area. At this time, n=2. If there is still no point in the cell bounding box in the intersecting region with reference to the point cloud, then continue to construct the cube region, where n is incremented in turn. If there is a point in the cell bounding box with reference point cloud, then in step S134, the closest distance calculating module 23 calculates the distance from all the points in the cell bounding box to the point, and obtains the closest distance d therein. 12 200912799 In step S135, the determination module 25 determines whether it is a heart (D+n*Step). Pure (D+n*SteP), the step is called 2, and the distance d is determined to be the closest distance from the point to the reference point cloud. Otherwise, if 'd> (D+n*Step)' is turned to be "the closest distance from the point to the moxibustion point cloud", then in step S136, the storage module 24 temporarily stores the distance d, which is denoted as dmin. 〆 Performing steps S131 and S132 described above to obtain a larger intersection area. Step Qing 37, the nearest distance calculation model (4) subtracts the intersecting region obtained from the previous parent region. In step S138, the determining module 25 traverses all the cell bounding boxes in the intersecting region obtained by the subtraction, and determines that all the cells in the bounding box are points in the reference point cloud. If there is no reference point cloud point, the above step 31, step phantom 32, step S137 and step S138 are repeatedly executed.乂 X If in step S138, it is determined that there is a reference point in the unit bounding box
=點’則步驟S139，所述最近距離計算模㈣計算該J ^包圍盒㈣所杨到該點的轉，並在該些距離值與 上述的dmin的值之間尋找一個最近距離d，。 步驟S140,判斷模組25判斷是否d、（D+n*step)。 +若d，> (D+n*Step) ’該距離d，不一定是該點到參考點 =的最近㈣，财步驟麗巾，儲存模組24暫存該距離 ，取代上述的d記作dmin。返回重複執行步驟sm、步驟 S132、步驟S137、步驟S138、步驟SU9及步驟§⑽。 13 200912799 否則右d 5 (D+n*Step)，則步驟S142中，確定該距 '離d’為該點到參考點雲的最近距離。 距齙^_钟，所述最近距離計算模組23得到上述最近 巨離所對應的參考點雲中的點。 方法本雲到點雲的最近距離計算系統及 -_占+_ 點雲構造包圍盒的方法，計算另 地減;雲的最近距離及對應的最近點，極大 4二:二進一步的，利用該方法的思想，也可以 。十，占丢到自由曲線、點雲到自由 由曲面的最近距離。以下，僅舉〜…及自由曲面到自 =1 的最近距離計算方法進行說明。 曲面:-斤L =，是本發明第二較佳實施例點雲到自由 曲面取近距離計算方法的實施流程圖。 ^自由 y驟320，接收一組點雲資料及一個自由曲， 該組點雲稱為移動點雲。 ，、中， 步驟S21，將上述自由 將自由曲面三角形角形網格化。所述 ^ ^格化疋將自__分0個4 步驟S22，將該自由曲 一組點雲，稱為參考點雲。中斤有二角形的頂點組成的 步驟S23,對該參考點雲構造人“ 所示。 圍益。坪細步驟同圖4 步驟S24,遍層所述的移動點雲， 步驟S25，根據上述^^中―個點。 可構造的包園盒，尋找 200912799 距離上述選擇的點最近的若干個單元包圍盒，透過計算該 點與該若干個單元包圍盒中的所有點的距離，得到該點到 參考點雲的最近距離，以及該最近距離所對應的參考點雲 中的最近點p。詳細步驟同圖5所示。 步驟S26，計算該選擇的點到以點p為頂點的若干三角 形的距離，得到其中的最近距離。 步驟S27，保存該最近距離。 步驟S28，遍曆上述移動點雲，判斷該移動點雲中是 否還有點沒有被選擇過。 若有，則返回步驟S23。否則，該流程結束。 參閱圖7所示，是本發明第三較佳實施例自由曲面到 自由曲面最近距離計算方法的實施流程圖。 步驟S30，接收兩個自由曲面。 步驟S31，將上述兩個自由曲面進行三角形網格化。 步驟S32，將其中一個自由曲面中所有三角形的中心 點組成的一組點雲，稱為移動點雲；將另一個自由曲面中 的所有三角形頂點組成一組點雲，稱為參考點雲。 步驟S33，對該參考點雲構造包圍盒。詳細步驟同圖4 所示。 步驟S34，遍曆所述的移動點雲，選擇其中一個點P0。 步驟S35，根據上述對參考點雲構造的包圍盒，尋找 距離點P0最近的若干個單元包圍盒，透過計算點P0與該若 干個單元包圍盒中的所有點的距離，得到點P0到參考點雲 的最近距離，以及該最近距離所對應的參考點雲中的最近 15 200912799 點p。詳細步驟同圖5所示。 步驟S36，計算點P0到以點p為頂點的若干三角形的距 離，得到其中的最近距離。 步驟S37，得到該最近距離所對應的以點p為頂點的三 角形。 步驟S38，計算點P0所在的三角形與上述得到的三角 形的距離d。 步驟S39，保存該距離d。 步驟S40，遍曆上述移動點雲，判斷該移動點雲中是 否還有點沒有被選擇過。 若有，則返回步驟S34。否則，步驟S41中，根據上述 計算出的最近距離，計算出該兩個自由曲面的平均距離， 即該兩個自由曲面的最近距離。 以上所述僅為本發明之較佳實施例而已，且已達廣泛 之使用功效，凡其他未脫離本發明所揭示之精神下所完成 之均等變化或修飾，均應包含在下述之申請專利範圍内。 【圖式簡單說明】 圖1是本發明點雲到點雲的最近距離計算系統較佳實 施例的硬體架構圖。 圖2是圖1中主機的功能模組圖。 圖3是本發明第一較佳實施例點雲到點雲的最近距離 計算方法的實施流程圖。 圖4是圖3中步驟S11對參考點雲構造包圍盒的具體 流程圖。 16 200912799 圖5是圖3中步驟S13計算一點到參考點雲最近距離 的具體流程圖。 圖6是本發明第二較佳實施例點雲到自由曲面最近距 離計算方法的實施流程圖。 圖7是本發明第三較佳實施例自由曲面到自由曲面最 近距離計算方法的實施流程圖。 【主要元件符號說明】 顯示器 1 主機 2 鍵盤 3 滑鼠 4 儲存單元 5 接收模組 20 包圍盒構造模組 21 選擇模組 22 最近距離計算模組 23 儲存模組 24 判斷模組 25 17= point', then step S139, the nearest distance calculation module (4) calculates the rotation of the J^ bounding box (4) to the point, and finds a closest distance d between the distance values and the value of the above dmin. In step S140, the determination module 25 determines whether or not d, (D+n*step). +If d,> (D+n*Step) 'The distance d is not necessarily the closest to the reference point = (4), the financial step, the storage module 24 temporarily stores the distance, instead of the above d Make dmin. The process returns to step sm, step S132, step S137, step S138, step SU9, and step § (10). 13 200912799 Otherwise right d 5 (D+n*Step), then in step S142, it is determined that the distance 'from d' is the closest distance of the point to the reference point cloud. From the 龅^_ clock, the nearest distance calculation module 23 obtains a point in the reference point cloud corresponding to the most recent large separation. Method: The nearest distance calculation system of the cloud to the point cloud and the method of -_ occupying the point cloud box of the +_ point cloud structure, calculate another ground reduction; the closest distance of the cloud and the corresponding nearest point, the maximum 4:2 further, using the The idea of the method can also be. Ten, accounted for the free distance from the free curve, point cloud to free by the surface. Hereinafter, only the method of calculating the nearest distance from ~... and the free-form surface to =1 will be described. The curved surface: - kg L = is a flow chart for implementing the method for calculating the close distance of the point cloud to the free curved surface according to the second preferred embodiment of the present invention. ^ Free y Step 320, receiving a set of point cloud data and a free song, the set of point clouds is called a mobile point cloud. , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , The ^^ 疋 疋 will be divided into 0 4 steps S22 from __, and the set of point clouds of the free curve is called a reference point cloud. The step S23 consisting of the vertices of the dimples has a step S23, and the reference point cloud constructor is shown. The enveloping step is the same as the step S24 of FIG. 4, and the moving point cloud is overlaid, step S25, according to the above ^ ^ 中-点. Constructable box, looking for 200912799 several unit bounding boxes closest to the selected point above, by calculating the distance between the point and all the points in the unit bounding box, get the point The nearest distance of the reference point cloud, and the closest point p in the reference point cloud corresponding to the closest distance. The detailed steps are the same as shown in Fig. 5. Step S26, calculating the distance of the selected point to several triangles with the point p as a vertex Step S27, the latest distance is saved. Step S28, traversing the moving point cloud to determine whether there are still points in the moving point cloud have not been selected. If yes, return to step S23. Otherwise, the The flow ends. Referring to Fig. 7, a flow chart of the method for calculating the closest distance of the free surface to the free surface according to the third preferred embodiment of the present invention is provided. Step S30, receiving two free surfaces. 31. The two free-form surfaces are triangularly meshed. Step S32, a set of point clouds composed of the center points of all the triangles in one of the free-form surfaces is called a moving point cloud; and all the triangles in the other free-form surface The vertices form a set of point clouds, which are called reference point clouds. Step S33, constructing a bounding box for the reference point cloud. The detailed steps are the same as those shown in Fig. 4. Step S34, traversing the moving point cloud, selecting one of the points P0 Step S35: Find a plurality of unit bounding boxes closest to the point P0 according to the bounding box constructed by the reference point cloud, and obtain a point P0 to the reference by calculating a distance between the point P0 and all the points in the plurality of unit bounding boxes. The closest distance of the point cloud and the last 15 200912799 points p in the reference point cloud corresponding to the closest distance. The detailed steps are the same as shown in Figure 5. Step S36, calculating the distance from point P0 to several triangles with the point p as the vertex, Obtaining the nearest distance among them. Step S37, obtaining a triangle corresponding to the closest distance with the point p as a vertex. Step S38, calculating the triangle where the point P0 is located and the above obtained The distance d of the angle is determined. Step S39, the distance d is saved. Step S40, traversing the moving point cloud, and determining whether there are still points in the moving point cloud have not been selected. If yes, returning to step S34. Otherwise, in step S41 Calculating the average distance of the two free curved surfaces, that is, the closest distance of the two free curved surfaces according to the calculated nearest distance. The above description is only a preferred embodiment of the present invention, and has been widely used. Equivalent changes or modifications made without departing from the spirit of the present invention should be included in the scope of the following claims. BRIEF DESCRIPTION OF THE DRAWINGS Figure 1 is the most recent point cloud to point cloud of the present invention. A hardware architecture diagram of a preferred embodiment of a distance computing system. 2 is a functional block diagram of the host of FIG. 1. 3 is a flow chart showing an implementation of a method for calculating a closest distance from a point cloud to a point cloud according to a first preferred embodiment of the present invention. Figure 4 is a detailed flow chart of the reference point cloud construction bounding box in step S11 of Figure 3. 16 200912799 FIG. 5 is a specific flow chart of calculating the closest distance of a point to the reference point cloud in step S13 of FIG. 3 . Fig. 6 is a flow chart showing the implementation of a method for calculating the closest distance from a point cloud to a free-form surface according to a second preferred embodiment of the present invention. Fig. 7 is a flow chart showing the implementation of the method for calculating the closest distance from the free-form surface to the free-form surface according to the third preferred embodiment of the present invention. [Main component symbol description] Display 1 Host 2 Keyboard 3 Mouse 4 Storage unit 5 Receiver module 20 Bounding box structure module 21 Selection module 22 Nearest distance calculation module 23 Storage module 24 Judgment module 25 17