LibreCAD V3 Beziers and File I/O
LibreCAD v3 Bezier and File IO project involves further development of the LibreCAD v3 Kernel and LibreCAD Software itself. LibreCAD at the moment is at very beginning stage of its development and lacks many features to be a robust kernel and a Solid Usable Software. LibreCAD v3 Evolution considers this issue and tends to implement 3 featues in this kernel.
- Input Output to the Drawing Files ( DXF Format )
- bezier implementation in kernel ( Quadratic )
- bezier splitting operation
- bezier bounding box
- bezier intersections
LibreCAD 3 kernel was developed by RVT in 2012 as an improvement over the LibreCAD v2 leveraging the power of
- C++ 11, Qt5, C++ Smart Pointers.
- concurrency support.
- Smart Data structures ( Quadtree implementation and the Visitor pattern for entities ).
- Modularity ( Separation of LibreCAD Kernel from the Viewer and the UI Portion).
- Pluggable backend for IO ( Database, File, Network Sharing ).
File input output in DXF module
A partial implementation of DXF read was made. This time it extends to include write to DXF support. Write to dxf constitutes of writing methods that will parse the LibreCAD document ( In memory while it is running ) and then convert them into objects that are supported by LibDXFrw which will write all the entities to a file.
- https://github.com/LibreCAD/LibreCAD/blob/master/librecad/src/lib/filters/rs_filterdxfrw.cpp // Reference for library usage as well as interacting with the document ( rough idea, this might be different from the way LC3 kernel is developed).
- https://sourceforge.net/p/libdxfrw/code/ci/master/tree/dwg2dxf/main.cpp // For library usage.
Bezier curves are parametric curves which are used in computer graphics to generate smoother curves. Bezier curves are very much useful for drawing curves in computer aided geometry. Bezier curves are also used in other vector graphics softwares like Coreldraw, Photoshop, Inkscape. These paths are not bound by limits of rasterized images and can be modified. Usually bezier curves used in computer graphics have a limited degree.
Linear equation of BC:
P(t)= (1-t)P0 + (t)P1
or we can write it as:
x = ( 1 – t ) x1 + ( t ) x2
y = ( 1 – t ) y1 + ( t ) y2
where t is the parameter, that help us to calculate value of x, y at specific point on the curve.
Quadratic equation of BC(3 control points):
P(t) = ( 1 – t ) 2P0 + 2 ( 1 – t ) ( t ) P1 + ( t )2P2
The terms ( 1 – t ) ^ 2 , t ( 1 – t ) and t2
are called Blending points or Basis Functions or Bernstein polynomials. These basis functions actually define how much the curve would get attracted towards a control point. Order in which the control points are given, affects the shape of curve. The degree of a bezier curve is always 1 less than the number of control points. A bezier curve having 1 control point has a degree of 2 and is represented as
ax ^ 2 + bx + c
A bezier curve having 2 control points has a degree of 3 and is represented as
ax ^ 3 + bx ^ 2 + cx + d
In Bezier implementation a class will be developed to handle bezier geometry details. Start point, End point, Control Point. Just for information the bezier curve of degree 2 is going to be implemented. ( Will form a quadratic eqauation ).
After this, another class will be implemented which will handle some basic operations on bezier, Scale, Copy, Move.
Bezier related functions will be implemented for eg, the coordinates value at some instance ( between 0 and 1 ) using the “De Casteljau” algorithm.
De Casteljau’s algorithm is a recursive method to evaluate polynomials in Bernstein form or Bézier curves, named after its inventor Paul de Casteljau. This algorithm is numerically stable in performing interpolation of points.
The advantage of De Casteljau’s algorithm is De Casteljau’s algorithm can also be used to split a single Bézier curve into two Bézier curves at an arbitrary parameter value. first you run the De Casteljau’s algorithm on the list of coordinates you have ( the start point, end point and the 1 control point ), it will return a list of two coordinates ( start and end of new line ) on which it will find the linear interpolation.
Bezier Bounding Box
Bounding box for a quadratic bezier curve tends to be simple. we have the start and end values of the bezier curve. We run the De Casteljau’s algorithm on the list of coordinates ( start, end, angle ) and we achieve the values of x and y at different magnitudes of t. we find the maximum value of x and y and then draw a bounding box around the three coordinates ( start, end, maxima found via the De Casteljau’s algorithm ) Algorithm,
- Since its a quadratic equation, get the roots for the quadratic equation.
- for a given function f(x) = ax2 + bx + c,
- x can be found as
- discriminant = b ^ 2 – 4ac
- and x = -b + sqrt(discriminant) / 2a and -b + sqrt(discriminant) / 2a same for y.
- once we get the roots,
- Discard x value that’s lower than 0 or higher than 1, because Bézier curves only use the interval [0,1].
- Determine the lowest and highest value when plugging the values t=0, t=1 and each of the found roots into the original functions.
- the lowest value is the lower bound, and the highest value is the upper bound for the bounding box we want to construct.
As stated above with the “De Casteljau’s algorithm” we also find all the points we need to split up a Bézier curve into two, smaller curves, which taken together form the original curve. When we run the algorithm for any value t, we need to split a curve at that t value: one curve is defined by all the points found prior to our on curve point, with the other curve being defined by all the points after our on curve point. This way we get the bezier splitted curve values. This bezier curve splitting is something we might require in bezier intersections also. i.e next milestone.
- curve 1 can be defined as M = A.val + ( 1 – A ) * B.val
- Curve 2 can be defined as M = ( 1 – A ) * A.val + B.val
Using de Casteljau’s algorithm to split the curve we can now implement curve/curve intersection finding using a “divide and conquer” technique:
- Take two curves C1 and C2, and treat them as a pair.
- If their bounding boxes overlap, split up each curve into two sub curves with C1.1, C1.2, C2.1 and C2.2, form four new pairs (C1.1,C2.1), (C1.1, C2.2), (C1.2,C2.1), and (C1.2,C2.2).
- For each pair, check whether their bounding boxes overlap.
- If their bounding boxes do not overlap, discard the pair, as there is no intersection between this pair of curves.
- If there is overlap, rerun all steps for this pair.
- Once the sub curves we form are so small that they effectively occupy sub pixel areas, we consider an intersection found.
- Splitting : http://pomax.github.io/bezierinfo/#splitting
- DXF IO Support
- Beizer implementation
Timeline of Development
- Week 1 : 23 May to 27 May
- Week 2 : 30 May to 3 June
- Base implementation of the bezier curve.
- Implementation of De Casteljau’s algorithm.
- Direct calculation algorithm.
- Week 3 : 6 June to 10 June
- Bounding box for the bezier Curve
- Week 4 : 13 June to 17 June
- Week 5 : 20 June to 24 June
- bezier splitting operation implementation.
- Week 6 : 27 May to 1 July
- Week 7 : 4 July to 8 July
- Week 8 : 11 July to 15 July
- bezier intersections ( line/circle/arc/bezier ).
- Lua support for the bezier.
- Week 9 : 18 July to 22 July
- Week 10 : 25 July to 29 July // Mid Term Evaluation
- File IO Operations with Lua support as well.
- Week 11 : 1 August to 5 August
- Week 12 : 8 August to 12 August
- Unit Tests for the deliverables.
- Week 13 : 15 Aug to 23 Aug ( 6 Days )
- Code polish / bugs fixes / formatting etc.
- I will be available 40 to 48 hours a week.
- My interest in CAD programs.
- There is no CAD program till now which satisfies my needs exactly right now on Linux. LibreCAD meets my demands more than others.
- My previous GSoC was also in LibreCAD and since I with my mentor have laid the foundation of new LibreCAD, I consider LibreCAD 3 as my baby, So I want to contribute to make it to life.
- I wish to lift up the level of open source CAD and Linux.
- With previous Summer of codes done with CAD, I have gained more experience about the working of CAD. There is a great need of a person who basically has knowledge of softwares like AutoCAD, LibreCAD, BRLCAD, SolidWorks, NX and knowledge in field of machines, I being a mechanical engineer and a programmer have worked with and for CAD softwares listed above.
- Moreover, My college project was also first designed on solidworks and BRLCAD before bringing it to reality.
- I therefore can easily understand user requirements can and bring it to reality.
- At last my wish to work for open source/open source CAD and my passion for programming.