# Difference between revisions of "User:3bhady"

From BRL-CAD

(Coding Period) |
(→Activity Log For This Period) |
||

(37 intermediate revisions by 7 users not shown) | |||

Line 11: | Line 11: | ||

# Tomorrow I'll take a look at SVGNest and compare how they implement the NFP with what the paper suggests. Today I'm studying for my final exams in my University tomorrow. | # Tomorrow I'll take a look at SVGNest and compare how they implement the NFP with what the paper suggests. Today I'm studying for my final exams in my University tomorrow. | ||

# Finished Reading the required papers and took notes to start summarizing them. | # Finished Reading the required papers and took notes to start summarizing them. | ||

− | + | = Coding Period = | |

− | + | == May 27-June 15 == | |

− | + | === Required === | |

Final Exams period. | Final Exams period. | ||

− | Delivering summary on the related papers. (O) | + | * Delivering summary on the related papers. (O) |

− | Investigating SVGNest JS library (structure, utilities). | + | * Investigating SVGNest JS library (structure, utilities). |

− | + | === Activity Log For This Period === | |

From 27/5 to 2/6 is my final exams week so my productivity won't be much and I'm making up for this time in the weekends and by working extra hours after 2/6. Deliverables won't be affected as I'm following the timeline for each period. | From 27/5 to 2/6 is my final exams week so my productivity won't be much and I'm making up for this time in the weekends and by working extra hours after 2/6. Deliverables won't be affected as I'm following the timeline for each period. | ||

# Investigated SVGNest C and JS code to find out what has changed between these two projects and if I can make use of the C implementation. | # Investigated SVGNest C and JS code to find out what has changed between these two projects and if I can make use of the C implementation. | ||

# Took notes on the related papers and started summarizing them. | # Took notes on the related papers and started summarizing them. | ||

# Designing bounding object function to get a 2d boundaries for the objects to work with. | # Designing bounding object function to get a 2d boundaries for the objects to work with. | ||

− | + | # Finished my final exams and working full time. | |

− | + | # Faced some issues with wxWidgets library and trying to fix them. | |

− | Extract useful functions from SVGnest JS. | + | # Continued working on designing an efficient bounding object function to get 2D outer contours of 3D objects to work on them. I've looked for similar function in the current 2D preview functionality in the application but the method I want isn't there so I'll continue coding it. |

− | Write skeleton for unit tests for extracted functions.(T) | + | # Tried concave hull and found papers on generating a bounding concave object to generate a 2D equivalent for the objects but I found that there are some cases that concave hull will fail in so we'll need convex hull. |

− | + | # Created a class "BoundingHull" to hold the bounding shape to transform 3D into 2D and still maintain the boundaries of the object so that no two objects would intercept with each other. | |

− | + | # Eid Elfetr Holiday so I'm working between family visits. | |

− | + | # Completed [https://github.com/3bhady/Slic3r/commit/ce678e817fb82642c68da1bd545a3bbddcee8325 calculating bounding hull] for each model with each copy of it after applying transformations on it. | |

− | + | # Going through SVGNest code to find important functions to start writing tests for them. | |

− | Write unit test for the geometry functions to be used.(T) | + | # Debugging SVGNest JS code and commenting on it while comparing the code to the papers. |

− | Implement the geometry utility functions.(C) | + | # Added comments and played with functions in SVGNest JS library and compared it to the read papers. Summary of the papers would make more sense being written into the code to help later in porting each function which relates to how each function contributes to the whole algorithm. |

− | + | # Forked the SVGNest repo and commenting on it [https://github.com/3bhady/svgnest here] | |

− | + | ||

− | + | == June 15-June 20 == | |

− | + | === Required === | |

− | Writing unit test skeleton for placement algorithm.(T) | + | * Extract useful functions from SVGnest JS. |

− | + | * Write skeleton for unit tests for extracted functions.(T) | |

− | + | === Activity Log For This Period === | |

− | + | * NFP (No Fit Polygon) is the core of the polygon packing algorithm but it makes more sense to start with implementing it now and port helper functions along the way to understand the functions being ported more as Their use appears instead of porting helper functions by themselves. | |

− | + | # Creating the basics of the NFP function. | |

− | Implementing unit testing for placement algorithm.(T) | + | # Continuing porting NFP function and useful functions which are required for it to run. |

− | Implementing placement algorithm.(C) | + | # Calculated the touching edges for polygons to help creating the NFP. |

− | Parallelizing the placement algorithm.(C) | + | # Generated the translation vectors for orbiting shape to slide alongside the stationary shape. |

− | + | ||

− | + | == June 20 -June 28 == | |

− | + | === Required === | |

− | + | * Write unit test for the geometry functions to be used.(T) | |

− | Design skeleton code for unit testing optimization algorithm.(T) | + | * Implement the geometry utility functions.(C) |

− | ==== Activity Log For This Period | + | === Activity Log For This Period === |

+ | * All the following functions are utility functions used in the NFP function which is the core of the packing algorithm this was supposed to be implemented next month but it makes sense to start with it and porting each helper function along the way. | ||

+ | # Started rejecting the translation vectors which will cause intersection. | ||

+ | # Wrote a skeleton code for a function to calculate the maximum distance a polygon can slide in a given direction without intersecting with another polygon. | ||

+ | # Created a function that takes two edges and finds the maximum distance one edge can travel in a given direction without intersection. | ||

+ | # Found each possible arrangement for the edges to be in without intersecting with each other. | ||

+ | # Created a function to calculate the maximum distance a vertex can travel in a given direction. | ||

+ | # Finished calculating the maximum sliding distance for each translation vector. | ||

+ | # Day off studying for a job interview wish me luck. | ||

+ | |||

+ | == June 28-July 4 == | ||

+ | === Required === | ||

+ | * Writing unit test skeleton for placement algorithm.(T) | ||

+ | === Activity Log For This Period === | ||

+ | # Fixing the flow in the NFP function as it wasn't working correctly. | ||

+ | # Development laptop got stuck in a login loop after installing CUDA so I spent the whole day trying to fix it. | ||

+ | # Continued modifying and fixing the NFP function. | ||

+ | # Debugging and fixing issues with the placement algorithm. ( the NFP had very large values ) | ||

+ | |||

+ | == July 4- July 21 == | ||

+ | === Required === | ||

+ | * Implementing unit testing for placement algorithm.(T) | ||

+ | * Implementing placement algorithm.(C) | ||

+ | * Parallelizing the placement algorithm.(C) | ||

+ | === Activity Log For This Period === | ||

+ | * Taking two days off to finish my graduation project. (I've already started working on this period's work 2 weeks ago). | ||

+ | * Debugging and tracing the placement algorithm. | ||

+ | * Fixing issues with the Point and Pointf in the placement algorithm as what everything should be. | ||

+ | * Fixed issues with trimming the vectors as it wasn't working correctly. | ||

+ | * Designed test case for the placement algorithm. | ||

+ | * Continued working on the placement algorithm and fixed issues with sliding as it wasn't moving correctly. | ||

+ | * Solved couple of issues as it was producing some garbage values. | ||

+ | * Looked for a way to visualize it's output to understand the results better. | ||

+ | * Fixed multiple issues where the variables names were wrong like replacing next_A_index with prev_A_index which were causing wrong results. | ||

+ | * Fixed issue with the starting point. | ||

+ | * Fixed issues with polygon slide distance. | ||

+ | * Fixed issues with segment distance. | ||

+ | * Created NFP for convex shapes. | ||

+ | * Working on moving the objects to a point on the NFP. | ||

+ | * Finished moving objects and now they are packed close to each other. | ||

+ | * Found an interesting method which takes a simpler and much faster approach to the NFP problem but needs at least one of the shapes to be convex which fits perfectly to our problem as we're starting with a convex hull for each shape. | ||

+ | |||

+ | == July 21-July 26 == | ||

+ | === Required === | ||

+ | * Design skeleton code for unit testing optimization algorithm.(T) | ||

+ | === Activity Log For This Period === | ||

+ | * Continued working on the placement algorithm as I took a new simpler approach and read multiple papers with simpler and faster approaches than the orbiting polygon with sliding edges presented in the SVGNest library. | ||

+ | # [http://www.diva-portal.org/smash/get/diva2:699750/FULLTEXT01.pdf "JONAS LINDMARK Thesis at CSC"] | ||

+ | # "A comprehensive and robust procedure for obtaining the nofit polygon using Minkowski sums" Which I thank [https://www.researchgate.net/profile/Julia_Bennell JULIA A BENNELL] for providing me with the full text when I requested it. | ||

+ | # Fixed the IFP with orbital approach. | ||

+ | |||

+ | == July 26-Aug 9 == | ||

+ | === Required === | ||

+ | * Implementing unit testing for optimization algorithm. (T) | ||

+ | * Implementing optimization algorithm.(C) | ||

+ | * Determining threshold for when to stop optimizing. | ||

+ | * Adding needed buttons in GUI for allowing user to specify threshold for stopping optimization. (C) | ||

+ | === Activity Log For This Period === | ||

N/A | N/A | ||

− | + | == Aug 9-Aug 19 == | |

− | + | === Required === | |

− | + | * Testing the whole auto-arranging module against SVGnest library and fixing bugs if the outputs are not identical. (T) | |

− | + | * Testing the output through the perl GUI. (T) | |

− | + | === Activity Log For This Period === | |

− | |||

− | |||

− | |||

− | |||

− | |||

− | Testing the whole auto-arranging module against SVGnest library and fixing bugs if the outputs are not identical. (T) | ||

− | Testing the output through the perl GUI. (T) | ||

− | |||

N/A | N/A | ||

Line 69: | Line 118: | ||

----------------------------------------------------------- | ----------------------------------------------------------- | ||

Deliverables are marked in the timeline as follows: | Deliverables are marked in the timeline as follows: | ||

− | Code is marked as (C). | + | * Code is marked as (C). |

− | Tests are marked as (T). | + | * Tests are marked as (T). |

− | Others are marked as (O). | + | * Others are marked as (O). |

+ | |||

+ | Code and comments on existing code can be found on my forks [https://github.com/3bhady/Slic3r Slic3r] [https://github.com/3bhady/SVGnest SVGNest]. |

## Latest revision as of 23:14, 30 July 2019

## Contents

# Community Bonding Period[edit]

- Played around with code and build GUI.
- Found where is auto-arrange is being called and how it's called so that I could get a grasp of how it should be replaced. Supermill helped by giving me another use of auto-arrange.
- Looked for a faster way to build the project rather than waiting for 15 minutes when changing anything, LoH helped me with a faster way to build it.
- Investigated SVGNest JS code to get a feel of how the code is structured.
- Started investigating in the SVGNest desktop application as gege2b has pointed out there is an implementation in C for SVGNest. After investigating I found the implementation isn't fully in C only one function of it is C and the rest is the previous JS code.
- Today I'll start reading one of the papers.
- I've started reading "Complete and robust no-fit polygon generation for the irregular stock cutting problem" paper and it was very helpful. I went through the rabbit hole as the paper references other papers so I dived head first into reading them. I got a better understanding of the No-Fit Polygon and what role does it play in the whole auto-arrange algorithm, why it's useful and why it's better than it's predecessors.
- Tomorrow I'll take a look at SVGNest and compare how they implement the NFP with what the paper suggests. Today I'm studying for my final exams in my University tomorrow.
- Finished Reading the required papers and took notes to start summarizing them.

# Coding Period[edit]

## May 27-June 15[edit]

### Required[edit]

Final Exams period.

- Delivering summary on the related papers. (O)
- Investigating SVGNest JS library (structure, utilities).

### Activity Log For This Period[edit]

From 27/5 to 2/6 is my final exams week so my productivity won't be much and I'm making up for this time in the weekends and by working extra hours after 2/6. Deliverables won't be affected as I'm following the timeline for each period.

- Investigated SVGNest C and JS code to find out what has changed between these two projects and if I can make use of the C implementation.
- Took notes on the related papers and started summarizing them.
- Designing bounding object function to get a 2d boundaries for the objects to work with.
- Finished my final exams and working full time.
- Faced some issues with wxWidgets library and trying to fix them.
- Continued working on designing an efficient bounding object function to get 2D outer contours of 3D objects to work on them. I've looked for similar function in the current 2D preview functionality in the application but the method I want isn't there so I'll continue coding it.
- Tried concave hull and found papers on generating a bounding concave object to generate a 2D equivalent for the objects but I found that there are some cases that concave hull will fail in so we'll need convex hull.
- Created a class "BoundingHull" to hold the bounding shape to transform 3D into 2D and still maintain the boundaries of the object so that no two objects would intercept with each other.
- Eid Elfetr Holiday so I'm working between family visits.
- Completed calculating bounding hull for each model with each copy of it after applying transformations on it.
- Going through SVGNest code to find important functions to start writing tests for them.
- Debugging SVGNest JS code and commenting on it while comparing the code to the papers.
- Added comments and played with functions in SVGNest JS library and compared it to the read papers. Summary of the papers would make more sense being written into the code to help later in porting each function which relates to how each function contributes to the whole algorithm.
- Forked the SVGNest repo and commenting on it here

## June 15-June 20[edit]

### Required[edit]

- Extract useful functions from SVGnest JS.
- Write skeleton for unit tests for extracted functions.(T)

### Activity Log For This Period[edit]

- NFP (No Fit Polygon) is the core of the polygon packing algorithm but it makes more sense to start with implementing it now and port helper functions along the way to understand the functions being ported more as Their use appears instead of porting helper functions by themselves.

- Creating the basics of the NFP function.
- Continuing porting NFP function and useful functions which are required for it to run.
- Calculated the touching edges for polygons to help creating the NFP.
- Generated the translation vectors for orbiting shape to slide alongside the stationary shape.

## June 20 -June 28[edit]

### Required[edit]

- Write unit test for the geometry functions to be used.(T)
- Implement the geometry utility functions.(C)

### Activity Log For This Period[edit]

- All the following functions are utility functions used in the NFP function which is the core of the packing algorithm this was supposed to be implemented next month but it makes sense to start with it and porting each helper function along the way.

- Started rejecting the translation vectors which will cause intersection.
- Wrote a skeleton code for a function to calculate the maximum distance a polygon can slide in a given direction without intersecting with another polygon.
- Created a function that takes two edges and finds the maximum distance one edge can travel in a given direction without intersection.
- Found each possible arrangement for the edges to be in without intersecting with each other.
- Created a function to calculate the maximum distance a vertex can travel in a given direction.
- Finished calculating the maximum sliding distance for each translation vector.
- Day off studying for a job interview wish me luck.

## June 28-July 4[edit]

### Required[edit]

- Writing unit test skeleton for placement algorithm.(T)

### Activity Log For This Period[edit]

- Fixing the flow in the NFP function as it wasn't working correctly.
- Development laptop got stuck in a login loop after installing CUDA so I spent the whole day trying to fix it.
- Continued modifying and fixing the NFP function.
- Debugging and fixing issues with the placement algorithm. ( the NFP had very large values )

## July 4- July 21[edit]

### Required[edit]

- Implementing unit testing for placement algorithm.(T)
- Implementing placement algorithm.(C)
- Parallelizing the placement algorithm.(C)

### Activity Log For This Period[edit]

- Taking two days off to finish my graduation project. (I've already started working on this period's work 2 weeks ago).
- Debugging and tracing the placement algorithm.
- Fixing issues with the Point and Pointf in the placement algorithm as what everything should be.
- Fixed issues with trimming the vectors as it wasn't working correctly.
- Designed test case for the placement algorithm.
- Continued working on the placement algorithm and fixed issues with sliding as it wasn't moving correctly.
- Solved couple of issues as it was producing some garbage values.
- Looked for a way to visualize it's output to understand the results better.
- Fixed multiple issues where the variables names were wrong like replacing next_A_index with prev_A_index which were causing wrong results.
- Fixed issue with the starting point.
- Fixed issues with polygon slide distance.
- Fixed issues with segment distance.
- Created NFP for convex shapes.
- Working on moving the objects to a point on the NFP.
- Finished moving objects and now they are packed close to each other.
- Found an interesting method which takes a simpler and much faster approach to the NFP problem but needs at least one of the shapes to be convex which fits perfectly to our problem as we're starting with a convex hull for each shape.

## July 21-July 26[edit]

### Required[edit]

- Design skeleton code for unit testing optimization algorithm.(T)

### Activity Log For This Period[edit]

- Continued working on the placement algorithm as I took a new simpler approach and read multiple papers with simpler and faster approaches than the orbiting polygon with sliding edges presented in the SVGNest library.

- "JONAS LINDMARK Thesis at CSC"
- "A comprehensive and robust procedure for obtaining the nofit polygon using Minkowski sums" Which I thank JULIA A BENNELL for providing me with the full text when I requested it.
- Fixed the IFP with orbital approach.

## July 26-Aug 9[edit]

### Required[edit]

- Implementing unit testing for optimization algorithm. (T)
- Implementing optimization algorithm.(C)
- Determining threshold for when to stop optimizing.
- Adding needed buttons in GUI for allowing user to specify threshold for stopping optimization. (C)

### Activity Log For This Period[edit]

N/A

## Aug 9-Aug 19[edit]

### Required[edit]

- Testing the whole auto-arranging module against SVGnest library and fixing bugs if the outputs are not identical. (T)
- Testing the output through the perl GUI. (T)

### Activity Log For This Period[edit]

N/A

Deliverables are marked in the timeline as follows:

- Code is marked as (C).
- Tests are marked as (T).
- Others are marked as (O).

Code and comments on existing code can be found on my forks Slic3r SVGNest.