Looking for breakthrough ideas for innovation challenges? Try Patsnap Eureka!

Local geometric feature-based efficient discrete geodesic line paralleling method

A technology of local geometric features and geodesics, which is applied in the details of image processing hardware, image data processing, 3D modeling, etc. It can solve the problem of insufficient parallelization of PCH, improve algorithm efficiency, and make full use of computing resources. , the effect of reducing operation time

Active Publication Date: 2018-10-30
TIANJIN UNIV
View PDF4 Cites 3 Cited by
  • Summary
  • Abstract
  • Description
  • Claims
  • Application Information

AI Technical Summary

Problems solved by technology

However, after the PCH parallelizes window element propagation and derivation, a serial operation is still required to organize the newly generated sub-window elements and add them to the priority queue. The parallelization of PCH is not complete enough.

Method used

the structure of the environmentally friendly knitted fabric provided by the present invention; figure 2 Flow chart of the yarn wrapping machine for environmentally friendly knitted fabrics and storage devices; image 3 Is the parameter map of the yarn covering machine
View more

Image

Smart Image Click on the blue labels to locate them in the text.
Viewing Examples
Smart Image
  • Local geometric feature-based efficient discrete geodesic line paralleling method
  • Local geometric feature-based efficient discrete geodesic line paralleling method
  • Local geometric feature-based efficient discrete geodesic line paralleling method

Examples

Experimental program
Comparison scheme
Effect test

Embodiment 1

[0035] In order to achieve the above purpose, the embodiment of the present invention proposes a propagation dependency graph (propagatio dependency graph, PDG) based on local geometric information, and for an edge-based geodesic algorithm, it includes the following two categories:

[0036] The first type of window element, such as figure 2 As shown, the geodesic information on edge e comes from: its own window element [1] Information, the window element information on the vertex v, and the opposite side e of the other two half-edge structures in the triangle l , e r The window element information on the edge e, that is, the opposite edge e of the upper half edge of the edge e l and the opposite side e of the next half side r .

[0037] The second type of window element, such as image 3 shows that the geodesic information on point v comes from: the window element information e on all adjacent sides 1 ,e 3 ,e 4 ,e 6 ,e n and all window element information e on oppos...

Embodiment 2

[0049] The scheme in embodiment 1 is further introduced below in conjunction with specific examples, see the following description for details:

[0050] 201: Initialize the buffer, and update the window element information related to the starting point;

[0051] 202: Build multiple vertex threads to process each point update event in parallel;

[0052]203: Each vertex v in the grid model actively updates its own value according to its own topological relationship, that is, according to its associated edge e 1 , e 2 ,...,e n to update the geodesic distance of the point, such as Figure 4 shown.

[0053] 204: Create a window element v on the opposite side through its own geodesic distance, and the created window element is stored in the buffer zone of the opposite side e;

[0054] 205: Build multiple side threads to process window element derived events on each side in parallel;

[0055] Because for a triangular mesh, there are only two kinds of sub-windows generated by de...

Embodiment 3

[0066] In the experiment, the AWP algorithm was compiled in the CUDA8.0 environment, and three different NVIDIA GPUs were used for comparative experiments. The three graphics cards are: GTX 970 with 1664 CUDA cores and 2.44Tflops computing power; 3072 CUDA cores with 7.0 Tflops of GTX TitanX and 3840CUDA cores, 12Tflops of TitanXp. Other geodesic classic serial algorithms are tested on a machine configured with i7-7700K, 4.2GHz CPU and 32G memory.

[0067] Since the algorithms involved in the experiment are divided into two types, for the exact algorithm, the evaluation algorithm is mainly based on the time and memory used by the algorithm and the number of intermediate variable window elements generated; for the approximate algorithm, the evaluation algorithm In addition to the time and memory used by the algorithm and the number of intermediate variable window elements, the mean square error (MSE) is used as the accuracy of the approximate algorithm. MSE can evaluate the deg...

the structure of the environmentally friendly knitted fabric provided by the present invention; figure 2 Flow chart of the yarn wrapping machine for environmentally friendly knitted fabrics and storage devices; image 3 Is the parameter map of the yarn covering machine
Login to View More

PUM

No PUM Login to View More

Abstract

The invention discloses a local geometric feature-based efficient discrete geodesic line paralleling method. The method comprises the following steps of: constructing a local geodesic information transfer topological structure; inputting a network model, initiatively updating own distance values by all the peaks in the network model, and deriving new pseudo-source point elements, namely, new second-type window elements; initiating deriving new window elements by edge window elements in first-type window elements, and storing the new window elements into buffer areas corresponding to the edges;establishing a plurality of edge threads to process a window element derivation event on each edge in parallel; creating a plurality of edge threads to process a window element collection event on each process in parallel; initiatively obtaining own sub-window elements by the edges according to own topological relationships; initiatively collecting window elements in a corresponding buffer area by the edge e and writing the collected window elements into a rolling array corresponding to the next state of rolling arrays; exchanging the rolling array; and if updatable second-type window elements exist, re-inputting the network mode l, and otherwise, ending the operation. According to the method, the algorithm efficiency is improved, the operation time is shortened and complete paralleling is realized.

Description

technical field [0001] The invention relates to computer graphics, computational geometry, parallel computing, high-performance computing neighborhood, and the technical field of CUDA (Compute Unified Device Architecture), in particular to a high-efficiency discrete geodesic parallel method based on local geometric features. Background technique [0002] The geodesic problem is an important problem in the field of computer graphics. At present, there is a large amount of literature on geodesic problems. For the discrete geodesic problem, we mainly start with numerical methods and geometric methods. [0003] The numerical-based geodesic solution method is mainly solved by the method of differential geometry. The theory of surfaces in differential geometry arises from the study of geodesic problems on surfaces. Numerical-based geodesic calculation methods have been continuously improved, but these methods still have defects, mainly manifested as non-reusability, lack of par...

Claims

the structure of the environmentally friendly knitted fabric provided by the present invention; figure 2 Flow chart of the yarn wrapping machine for environmentally friendly knitted fabrics and storage devices; image 3 Is the parameter map of the yarn covering machine
Login to View More

Application Information

Patent Timeline
no application Login to View More
Patent Type & Authority Applications(China)
IPC IPC(8): G06T17/20
CPCG06T17/20G06T2200/28
Inventor 于瑞国傅旭洲喻梅王建荣赵满坤高洁
Owner TIANJIN UNIV
Who we serve
  • R&D Engineer
  • R&D Manager
  • IP Professional
Why Patsnap Eureka
  • Industry Leading Data Capabilities
  • Powerful AI technology
  • Patent DNA Extraction
Social media
Patsnap Eureka Blog
Learn More
PatSnap group products

Browse by: Latest US Patents, China's latest patents, Technical Efficacy Thesaurus, Application Domain, Technology Topic, Popular Technical Reports.

© 2024 PatSnap. All rights reserved.Legal|Privacy policy|Modern Slavery Act Transparency Statement|Sitemap|About US| Contact US: help@patsnap.com