http___blog.simmakers.com_fast-volume-computing-algorithm__lang_bg_1.xml
http___blog.simmakers.com_fast-volume-computing-algorithm_.xml
1.1 2.1 2.2 2.3 2.4 3.1 4.1 5.1 5.2 6.1 6.2 6.3 7.1 7.2 7.3 8.1 9.1 9.2 9.3 9.4 10.1 10.2 10.3 10.4 11.1 11.2 12.1 12.2 13.1 13.2 13.3 14.1 15.1 16.1 16.2 16.3 16.4 17.1 17.2 17.3 17.4 18.1 18.2 19.1 19.2 19.3 20.1 20.2 21.1 22.1 23.1 24.1 24.2 25.1 25.2 26.1 27.1 28.1 29.1 29.2 29.3 29.4 29.5 30.1 30.2 30.3 30.4 30.5 30.6 30.7 30.8 30.9 30.10 30.11 30.12 30.13 31.1 32.1 32.2 32.3 32.4
Въвеждане Computing на обема на многостен в космоса 3D не е тривиален проблем, но следното тривиално метод съществува: разделяне на обема на прости пирамиди и преброяване на сумата от тези обеми. Обаче, тази методология е трудно за изпълнение, , както и че е много ресурси и бавно. Какво е по-, изчислителни алгоритъм съгласно тази методика е трудно да паралелизация. И като се отчитат тенденциите в областта на паралелни изчисления за развитие GPU, способността да се увеличи скоростта на изчислителна многократно се губи. В тази статия на алгоритъма за определяне на обема на произволна геометрия в 3D пространството по отношение на бързо изчислителна е описан. Входни данни Подготвителна стъпка. Правоъгълна мрежа (поз.1 на фиг.1) около геометрия (поз.2 на фиг.1) е изграден с помощта на нейното минимално и максимално координати. Потребителят избира правоъгълни параметри мрежата. Например, на броя клетки на мрежата може да се приема равен на броя на потока мулти-процесора на графичния процесор. Следователно, Нашата задача се превръща в компютри и последващо сумиране на обемите заети от фрагменти от геометрии в клетки, както е показано на фигура 2. Практически във всички случаи обекта се е съответен набор от триъгълници с подходящ байпас (или нормално). Този комплект може да се съхранява като цяло масивна и може да се обжалва пред него паралелно от всяка клетка или да извърши геометрия предварителна обработка за всички клетки. В този пример не описват геометрия за предварителна обработка за клетки, защото това е предмет на отделна тема за оптимизация. Алгоритъм на клетки обем определението: Стъпка 1. Извършва клипинг окото с помощта на кутия (мрежова клетка). С цел опростяване и ускоряване на алгоритъма, подрязване се извършва с помощта на 6 равнини, които образуват кутия. Clipping се извършва от всеки самолет последователно в произволен ред. Стъпка 2. За да проектираме върху XOY всички полигони, които правят подстригва окото. Изчислете обема на всяка една триъгълник. Обемите се изчисляват като суми на три пирамидални обеми, които представляват форма (виж фиг. 3). Стъпка 3. В зависимост от ориентацията на нормалната тези частични обеми са включени в сумата на обратното означаващо (означаващо на скаларното произведение на нормалната на полигон и равнина проекция). Стъпка 4. Изчислява площ на напречното сечение, образувана от горната повърхност прозорец (паралелно на проекционната равнина) и окото (виж фигурата 5). За да се изчисли целия обем на обекта вътре в кутията, че е необходимо не само да го нарежете с помощта на полето, но също така и за да го затворите (което е много време задача). За да добие силата на звука на всички правоъгълници се проектира върху кутията лицето. Следователно, е възможно да се опрости изчислителна схема, преработва само горната повърхност, защото прогнозите на други лица на полето лицето дават нулево площ. Изчислява сечението (виж фиг. 6) с промяната, описана по-долу. Модификация отчита незатворените случаи (многоъгълник може да премине ръбовете на горния прозорец лицето, В този случай ще се пресекат страни на правоъгълник) (виж фиг. 7). В такъв случай това е горният ръб на лицето трябва да формира двуизмерен заключване полигон. Отново, там се счита, че е необходимо да се изчисли заключване по всички краища на горната повърхност, това ще бъде достатъчно, за да се изчисли заключване само на горния ръб. По този начин, следващите операции се извършват на един сегмент. Още, терминът ръб ще означава, а именно ръба A на фиг. 8. Като текущи subproblem е намалена до едномерна, тогава всички геометрични понятия се използват в едномерен смисъл (проекция на линията). Например, нормалното (или всеки друг вектор нормализирано), фактически, е 1 или -1. Във връзка с тези норми двукомпонентни структура може да бъде разделена на ляво (1) и право (+1). Фигура 9 илюстрира схема на изчисляване на заключване на горния ръб. Краят е разделен на сегменти и всеки сегмент се определя от броя на нормалните. Имаме предвид, че броят на нормалните за един сегмент е броят на нормалните, насочени от дадения сегмент минус броя на нормалните насочени към този сегмент, също така е необходимо да се вземат предвид само тези норми на окото триъгълници, които имат точно една intercut с острието. Първоначално, целия ръб образува един сегмент източник с броя на нормалните равни 0. В зависимост от броя на паритет триъгълници, които пресичат границата, вътрешен (по отношение на окото) крайните сегменти могат да имат броя на нормалните равни 0 или 1. В зависимост от изпълнението на предходните стъпки на алгоритъма някои гранични ситуации могат да възникнат, например, като на фигура 10: Нека разгледаме случая, когато триъгълника пресича с ръб на сегмента AB (повече от една точка на пресичане). Сегмент AB трябва да бъде заключена от по-нататъшно компютри от нормалните по две причини: • Площта под този сегмент се взема под внимание, тъй като този сегмент е в списъка на двуизмерни повърхности на полигона; • Невъзможно е да проектира нормално върху ръба. Алгоритъм на проекта. На първата стъпка на алгоритъма за определяне на окото напречно сечение с всяка клетка, има случаи, когато сечение на мрежата с клетката не съществуват (клетката е вътре или извън). Ако напречното сечение на окото с клетка съществува, Тези клетки са маркирани като празна (безплатно). Още, е необходимо да се отбележи празни клетки, като клетките съществуващи или в обема на или извън обема. Например, за да маркирате с 0 ако клетките са от обема или стойността на клетъчния обем, ако сумата е включена в стойността. Можете да използвате един от двата алгоритми или тяхната комбинация: • Row-мъдър алгоритъм сканиране; • Алгоритъм на рекурсивни обем попълнете. И двете от тези алгоритми са широко дискутирани в Интернет. Същността на първия алгоритъм е следната: произволна посока е избран (например, заедно OZ ос).Самолетът по избраната посока е последователно за мача (например, XOY самолета в случай на OZ ос). Вие започвате да сканирате в самолета всеки ред, който е последователен набор от клетки по определена посока. Cells маркировката се намали до подчертаване празни клетки, докато всеки пълни клетка е изпълнено. Този алгоритъм има много ограничения, които трябва да се разглеждат поотделно (ако само 1 клетка на ред е изпълнен; ако 2 клетки са пълни, но те са началото на геометрията, и т.н.). Същността на втория алгоритъм се свежда до избора на всяка празна клетка и след това на рекурсивни анализ на съседните клетки и тяхното последващо допълнение към изброените опашката. Ако съсед клетка е пълна, тази клетка не е включена в опашката за пробата. Веднага след като е невъзможно да се избере клетка съсед, цялата последователност на клетките е маркиран като избраните клетки в определен обем. Следваща произволна клетка е избран и всички същите стъпки се провеждат. В резултат, празните клетки са отбелязани като принадлежащи към определен обем. Освен това е необходимо да се определи дали е избран обем пълни или празни. Това е сложността на алгоритъма. Най-простият случай е следната: в хода на рекурсия, веднага след като първата пълна клетка или граничен обем е там, анализ на целия обем вътре или извън се извършва. Анализ се извършва въз основа на нормалните на триъгълници, които образуват мрежа в окупирана клетка. Но тази операция е или отнема много време или ресурсоемка. Поради недостатъците на двете методики, е препоръчително да се прибегне до тяхната комбинация. Например, да използва само рекурсивно обем маркиране и след това прокарайте клетъчна линия с отбелязани обеми. Тази технология може да бъде много лесно паралелизирано. Заключение. По този начин, алгоритъма на изчисляване на обем от нито един мулти маршрута геометрия в пространството е въведено. Този алгоритъм може да се използва за определяне на размера на нефт или газ в областта. Видимо предимство на алгоритъма е способността му да паралелизацията и като резултат - бърз резултат, постигането. Недостатъкът на алгоритъма е сложността на неговото разбиране и прилагане.
1.1 2.1 2.2 2.3 2.4 3.1 4.1 5.1 5.2 6.1 6.2 6.3 7.1 7.2 7.3 8.1 9.1 9.2 9.3 9.4 10.1 10.2 10.3 10.4 11.1 11.2 12.1 12.2 13.1 13.2 13.3 14.1 15.1 16.1 16.2 16.3 16.4 17.1 17.2 17.3 17.4 18.1 18.2 19.1 19.2 19.3 20.1 20.2 21.1 22.1 23.1 24.1 24.2 25.1 25.2 26.1 27.1 28.1 29.1 29.2 29.3 29.4 29.5 29.6 30.1 30.2 30.3 30.4 30.5 30.6 30.7 30.8 30.9 30.10 30.11 30.12 30.13 31.1 32.1 32.2 32.3 32.4
Introduction Computing of the volume of polyhedron in 3D space isn’t a trivial problem, but the following trivial method exists: dividing the volume into simple pyramids and counting the sum of these volumes. However, this methodology is difficult for implementation, as well as it is resource-intensive and slow. What is more, computing algorithm according to this methodology is difficult to parallelize. And taking into account trends in the field of parallel computing on GPU development, the ability to increase the rate of computing repeatedly is being lost. In this article the algorithm for determining the volume of arbitrary geometry in 3D space in terms of fast computing is described. Input data Preparatory step. A rectangular grid (pos.1 on fig.1) around geometry (pos.2 on fig.1) is built using its minimum and maximum coordinates. User chooses rectangular grid parameters. For example, the number of grid cells can be taken equal to the number of stream multi-processors on GPU. Therefore, our task turns into computing and subsequent summing of the volumes occupied by fragments of geometries in cells, as shown on Figure 2. Practically in all cases object geometry is a corresponding set of triangles with an appropriate bypass (or normal). This set can be stored as a whole massive and you may appeal to it parallel from every cell or perform geometry pre-processing for all cells. In this example we don’t describe geometry pre-processing for cells, because this is the subject of a separate topic for optimization. Algorithm of cells volume definition: Step 1. Carry out mesh clipping by means of box (grid cell). To simplify and accelerate the algorithm, clipping is performed with the help of 6 planes that form a box. Clipping is performed by each plane alternately in any order. Step 2. To project onto XOY all polygons which make clipped mesh. Compute the volume under each triangle. The volumes are computed as the sums of three pyramid volumes, which form the shape (see Fig. 3). Step 3. Depending on the orientation of normal these partial volumes are included into the sum with opposite signifier (signifier of scalar product of the normal of polygon and projection plane). Step 4. Compute cross-sectional area formed by upper face box (parallel to projection plane) and mesh (see figure 5). In order to compute the entire volume of the object inside the box it is necessary not only to cut it by means of the box, but also to close it (which is a very time consuming task). In order to gain the volume all rectangles are projected onto the box face. Therefore, it is possible to simplify circuit computing, having processed only the upper face, because projections of other faces on box face give zero area. Compute cross-sectional area (see Fig. 6) with modification described below. Modification takes into account unclosed cases (polygon can cross edges of the upper face box, in this case it will cross faces of rectangle) (see fig. 7). In such case the upper edge of the face should form two-dimensional polygon locking. Again, there is considered the fact that it is no need to compute locking on all edges of the upper face, it will be enough to compute locking only on the upper edge. Thus, next operations take place on one segment. Further, the term edge will mean namely edge A on Fig. 8. As current subproblem has been reduced to one-dimensional, then all geometric concepts are used in one-dimensional sense (projection on the line). For example, the normal (or any other normalized vector), in fact, is 1 or -1. In connection with such binary structure normals can be divided into left (1) and right (+1). Figure 9 illustrates the scheme of computing the locking on top edge. The edge is divided into segments and each segment is determined by the number of normals. We mean that the number of normals of one segment is the number of normals directed from the given segment minus the number of normals directed to this segment, it is also necessary to take into account only those normals of mesh triangles, which have exactly one intercut with the edge. Initially, the whole edge forms a single source segment with the number of normals equal to 0. Depending on the parity number of triangles, which cross the edge, internal (relative to the mesh) edge segments may have number of normals equal to 0 or 1. Depending on the implementation of the previous steps of the algorithm some boundary situations may occur, for example, as on Figure 10: Let us consider the case when triangle intersects with the edge on a segment AB (more than one point of intersection). Segment AB needs to be locked from further computing of normals for two reasons: • The area under this segment is taken into account because this segment is on the list of two-dimensional faces of the polygon; • It is impossible to project the normal onto the edge. Algorithm completion. On the first step of the algorithm on determination of mesh cross-section with each cell, there are cases when cross-sections of the mesh with the cell do not exist (the cell is either inside or outside). If a cross-section of mesh with a cell exists, these cells are marked as empty (free). Further, it is necessary to mark empty cells as the cells existing either in the volume or out of the volume. For example, to mark with 0 if the cells are out of the volume or with the value of cell volume, if the amount is included in the value. You can use one of the two algorithms or their combination: • Row-wise scan algorithm; • Algorithm of recursive volume fill. Both of these algorithms are widely discussed on the Internet. The essence of the first algorithm is the following: arbitrary direction is selected (eg, along OZ axis). The plane along the chosen direction is consistently chosen (for example, XOY plane in case of OZ axis). You begin to scan on the plane each line which is a consistent set of cells along a particular direction. Cells marking is reduced to highlighting empty cells until any filled cell is met. This algorithm has many restrictions that need to be considered separately (if only 1 cell on the line is filled; if 2 cells are filled, but they are top of geometry, etc.). The essence of the second algorithm is reduced to the choice of any empty cell and then to the recursive analysis of neighbor cells and their subsequent addition to the sampling queue. If neighbor cell is full, this cell is not included in the queue for the sample. As soon as it is impossible to choose neighbor cell, the whole sequence of cells is marked as selected cells in a certain volume. Next arbitrary cell is selected and all the same steps are conducted. As a result, empty cells are marked as belonging to a particular volume. Further it is necessary to determine whether the selected volume is empty or filled. This is the complexity of the algorithm. The simplest case is the following one: in the course of recursion as soon as the first full cell or volume border is there, the analysis of the entire volume inside or outside is performed. Analysis is performed on the basis of the normals of triangles that make up the mesh in an occupied cell. But this operation is either time-consuming or resource-intensive. Due to the drawbacks of both methodologies, it is advisable to resort to their combination. For example, to use only a recursive volume marking and then pass the cell line with marked volumes. Such technology can also be quite easily parallelized. Conclusion. Thus, the algorithm of computing the volume of any multi-segment geometry in space has been introduced. This algorithm can be used for determination of oil or gas amount in the field. Apparent advantage of the algorithm is its ability to parallelization and as a result – rapid result achievement. The disadvantage of the algorithm is complexity of its understanding and implementation.