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.

std::map(milestones, commits)


Quadratic bezier First implementation,

Bezier in Viewer


Maths Improvement

Hoemogeneous Matrix method implementation

Intersections CleanUp and Eigen based implementation

Linear solver improvement ( Eigen’s ColPivHouseHolder )

Polynomial Solvers improvement ( Porting to eigen based solvers )


Bezier additional implementations

Length of Bezier

Nearest Points

Bounding box

Tangent and normal


Mirror Implmentation


DXF write implementation




Spline Improvement,


Cubic Beziers Implementation


Spline Intersections,

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.