The numeric based bezier/circle intersection

We were using bounding box method for finding intersections between cubic bezier and the circle/arcs that method was slow and I was looking for a better optimized version and which was definitely only possible by using a numerical solving method. We had to find intersections and recursion could have been the bottleneck in bounding box method. A better numerics based method has been implemented which is damn fast. I’ve been stuck on this for a long time, just breathed a sigh of relief.

Advertisements

std::map(milestones, commits)

Beziers

Quadratic bezier First implementation,

https://github.com/LibreCAD/LibreCAD_3/commit/881c7a771139aa68304f1cdefc8b6fa7cb27661b

Bezier in Viewer

https://github.com/LibreCAD/LibreCAD_3/commit/953669b00072d576b0ee623c97f3113e4fcc42ad

 

Maths Improvement

Hoemogeneous Matrix method implementation

https://github.com/LibreCAD/LibreCAD_3/commit/54a07a7668e70d99a73465ca53df04a17b866cca

Intersections CleanUp and Eigen based implementation

https://github.com/LibreCAD/LibreCAD_3/commit/5fdf3dbc2c964eaa39fb2bc7cd92a79995d42f52

Linear solver improvement ( Eigen’s ColPivHouseHolder )

https://github.com/LibreCAD/LibreCAD_3/commit/980db535c45429e3241816a4245f03a346b40d7f

Polynomial Solvers improvement ( Porting to eigen based solvers )

https://github.com/LibreCAD/LibreCAD_3/commit/d857053d69ac8774edebfab8bffd59b98c7e76ed

 

Bezier additional implementations

Length of Bezier

https://github.com/LibreCAD/LibreCAD_3/commit/8a8dd2218a9d35dd98fc895a4b4b98e85cac732d

Nearest Points

https://github.com/LibreCAD/LibreCAD_3/commit/64e319861a7e42821a9bd09c84ec8b18e7d7ffca

Bounding box

https://github.com/LibreCAD/LibreCAD_3/commit/0f4c9c3623f722b3f1197f696efbb345e9bd8532

Tangent and normal

https://github.com/LibreCAD/LibreCAD_3/commit/e5f2de20e045a50fc7459af08621c9132d0a185d

 

Mirror Implmentation

https://github.com/LibreCAD/LibreCAD_3/commit/53e0a5001a0389c0062b1c09e380bdc6b536c47e

https://github.com/LibreCAD/LibreCAD_3/commit/a53429946c8f6ea91b535818f357a16e0529a1bf

 

DXF write implementation

https://github.com/LibreCAD/LibreCAD_3/commit/dfc7f4b853cfbd54a3eda8cd5117499271024d28

https://github.com/LibreCAD/LibreCAD_3/commit/8d9faf1ca517e4afab59276990920adf2b9ac949

 

OpenNURBS

https://github.com/LibreCAD/LibreCAD_3/commit/75c9669448827b039498f4406a04ba806f14ed10

 

Spline Improvement,

https://github.com/LibreCAD/LibreCAD_3/commit/fda9dbcaea4732dc36e2ac82416712305a185578

https://github.com/LibreCAD/LibreCAD_3/commit/32fa8a02e8b538e2bd3a8cf333e077c946a7a734

 

Cubic Beziers Implementation

https://github.com/LibreCAD/LibreCAD_3/commit/34141d6e0f302f07b8f8c2b6d0fbc1a7f38e0947

 

Spline Intersections,

https://github.com/LibreCAD/LibreCAD_3/commit/f616277c95136103aae8d691391fd8a99927aabf

The testing and Documentations

So its the final week and I have worked on documentation mostly. wrote the docs for all the functionalities implemented this year involving beginning mathematics to the bezier and splines. Have created unit tests for most of the things that had mathematics. Some although are UI dependent since those were almost dependent on approximations. Like the intersections. Still I have covered almost everything what could be directly done, for the rest I have screenshots on blog that were posted as the things were being implemented.

The LibreCAD 3 Update!

This year the LibreCAD 3 had its development focused again on Kernel from my side. In the kernel portion of LibreCAD the main tasks to be developed this year were mostly related to mathematics. On an higher level of overview, we developed quadratic beziers, Cubic Beziers, Spline Support, DXF Write support, Mirrors implementation. We even opted for additional libraries to improve performance, robustness of our math portion ( Eigen Library ) and Adding spline support ( OpenNURBS ) to our LibreCAD.

Whats been done,

Quadratic beziers have following functionalities,

  • Move
  • Rotate
  • Scale
  • Mirror
  • Nearest point
  • Curve
  • Bounding Box
  • Tangent
  • Normal
  • Splitting
  • Line Bezier Intersection
  • Circle bezier Intersection
  • Arc bezier Intersection
  • Ellipse Bezier Intersection
  • Bezier Bezier Intersection

Cubic Bezier since was developed just to support cubic splines basically, It has support for all basic works

  • Move
  • Rotate
  • Scale
  • Mirror
  • Curve
  • Bounding Box
  • Splitting
  • Line Bezier Intersection
  • Circle bezier Intersection ( Need to be optimized )
  • Arc bezier Intersection ( Need to be optimized )
  • Bezier Bezier Intersection

Splines Support,

Splines have incorporated its support from OpenNURBS. When a spline is created, opennurbs does its work and spline is converted in to opennurbs curve. From this curve we are able to get splitted beziers which help in rendering the proper splines. These curves are also useful in getting intersections in spline and other entities. When ever we want intersection between spline and any other entity, we basically split spline into beziers and check intersections with the beziers.

So spline have similar operations like move/copy/rotate/scale which were implemented previously.

We just added intersections and proper rendering support for the splines.

Intersections supported are,

  • Line spline
  • Circle spline
  • Ellipse spline
  • Arc spline
  • Bezier Spline
  • Spline Spline

For quadratic splines all work well, the Cubic splines since are dependent on cubic beziers, the circle/arc spline intersections need to be optimized ( the cubic bezier basically )

Mirror Support

Mirror was implemented this year for most of the entities involving

  • Line
  • Arc,
  • Circle
  • Bezier
  • Ellipse
  • Spline
  • Except Text and Dimensions

Write DXF Support

We also added DXF writing support this year to the LibreCAD. The librecad is now able to export DXF files and that too with the support of layers and colors.

The entities/objects supported by DXF write are,

  • point
  • line
  • circle
  • arc
  • spline
  • ellipse
  • linetypes
  • Layers ( important )

Implementing layers support for DXF write, we have now implemented the color, line type support for DXF as well. Everything written here is 100% working although it might require an optimisation but everything here works.