numba + cuda: best way to re-organize my algorithm?
0 views
Skip to first unread message
Brian Merchant
Apr 29, 2016, 9:34:47 PM4/29/16
to Numba Public Discussion - Public
Hi all,
Say that you have U polygons, where each polygon has V vertices (that is, every polygon has the same number of vertices). One can consider line segments between each pair of points (A, x), (B, y), where A and B are polygon numbers, and x and y are vertex numbers.
My problem is to determine whether any such line segment (A, x), (B, y) intersects any polygon in the system.
My algorithm was initially designed for CPU execution, and took the following form (to answer the question "does the given line segment intersect with any polygon in the system?"):
1) does the line segment intersect with the polygon it originates from? if yes, return TRUE, else continue to 2)
2) does the line segment intersect with the polygon it ends at? if yes, return TRUE, else continue to 3)
3) does the line segment NOT intersect with the bounding box of any polygon apart from the ones it originates and ends at? if yes, return FALSE, else continue to 4)
4) for each polygon whose bounding box the line segment intersects with, check to see if each the line segment intersects with any edge -- if yes, return TRUE
I am now thinking of re-organizing my code for execution on a CUDA GPU. My thought is that instead of trying to faithfully translate the above algorithm, in order to take advantage of the massively-parallel capacity of the GPU, I should do the following:
Kernel: given two line segments, check to see if they intersect
Problem space: line segment of interest, all polygon edges in system
So, on each thread I would solve the problem: "does the line segment of interest intersect with the polygon edge assigned to this thread"? Much of the sophistication of the CPU algorithm (e.g. checking for bounding box intersections separately, checking to see if self-intersections apply, etc.) are thrown out of the window, in order to take advantage of the massively-parallel capacity of the GPU.
Does this make sense?
Kind regards,
Brian
Say that you have U polygons, where each polygon has V vertices (that is, every polygon has the same number of vertices). One can consider line segments between each pair of points (A, x), (B, y), where A and B are polygon numbers, and x and y are vertex numbers.
My problem is to determine whether any such line segment (A, x), (B, y) intersects any polygon in the system.
My algorithm was initially designed for CPU execution, and took the following form (to answer the question "does the given line segment intersect with any polygon in the system?"):
1) does the line segment intersect with the polygon it originates from? if yes, return TRUE, else continue to 2)
2) does the line segment intersect with the polygon it ends at? if yes, return TRUE, else continue to 3)
3) does the line segment NOT intersect with the bounding box of any polygon apart from the ones it originates and ends at? if yes, return FALSE, else continue to 4)
4) for each polygon whose bounding box the line segment intersects with, check to see if each the line segment intersects with any edge -- if yes, return TRUE
I am now thinking of re-organizing my code for execution on a CUDA GPU. My thought is that instead of trying to faithfully translate the above algorithm, in order to take advantage of the massively-parallel capacity of the GPU, I should do the following:
Kernel: given two line segments, check to see if they intersect
Problem space: line segment of interest, all polygon edges in system
So, on each thread I would solve the problem: "does the line segment of interest intersect with the polygon edge assigned to this thread"? Much of the sophistication of the CPU algorithm (e.g. checking for bounding box intersections separately, checking to see if self-intersections apply, etc.) are thrown out of the window, in order to take advantage of the massively-parallel capacity of the GPU.
Does this make sense?
Kind regards,
Brian
Diogo Silva
Apr 30, 2016, 6:00:22 AM4/30/16
to Numba Public Discussion - Public
Hi Brian,
How would you check for intersection of the input line segment and the bounding boxes of the polygons? Can't the line just go through a polygon without intersecting any of the segments connecting the edges?Diogo
--
You received this message because you are subscribed to the Google Groups "Numba Public Discussion - Public" group.
To unsubscribe from this group and stop receiving emails from it, send an email to numba-users...@continuum.io.
To post to this group, send email to numba...@continuum.io.
To view this discussion on the web visit https://groups.google.com/a/continuum.io/d/msgid/numba-users/e26b4bb6-4864-4b78-9bb7-e4acdb9486d8%40continuum.io.
For more options, visit https://groups.google.com/a/continuum.io/d/optout.
Reply all
Reply to author
Forward
0 new messages