DEV Community: compilelife

Simply understanding Bézier curves.

compilelife — Fri, 16 Aug 2024 00:55:39 +0000

Imagine if you could only use straight lines, ellipses, and circles, wouldn't it be difficult to design a car with smooth lines and a complex appearance?

In 1962, the French engineer Pierre Bézier published the Bézier curve, which was initially used for the main body design of cars.

Bézier curves can define a smooth curve through a series of control points. The curve always passes through the first and last control points and is influenced by the shape of the intermediate control points. Additionally, Bézier curves have the property of convex hulls.

Bézier curves are widely used in computer graphics and image modeling, such as in animation, font design, and industrial design.

Formula

Let's understand this.

P(t) represents a point on the curve at t (t is a fraction, with a value from 0 to 1). What is a point on the curve at t? A common curve description is: y = f(x), and for now, let's understand P(t) as f(x). The difference is that P(t) is a parametric representation (and the calculation result is a "vector" like [x, y]), which will be explained in detail later.

Next, Pi represents the i-th control point (i starts from 0). Taking the above figure as an example, there are 4 control points, which are P0, P1, P2, P3. The n in the formula is the last index of the control points, that is, n = 3 (note that it is not the number of control points, but the count minus 1).

Bi,n(t) is the Bernstein basis function, also known as the basis function. For each specific (i, n), there is a different basis function corresponding to it. If you understand from a weighted perspective, you can consider the basis function as a weight function, indicating the "contribution" of the i-th control point Pi to the curve coordinates at the position of t.

The formula for the basis function is as follows:

$(ni)\binom{n}{i}$ Is the combination number (how many ways to choose i out of n?). As for why the basis function looks like this, it can be understood in connection with the De Casteljau algorithm (see later in the text)

Back to the P(t) formula, $∑i=0n\sum_{i=0}^{n}$ is the summation symbol, indicating that the subsequent part ( $Bi,n(t)⋅PiB_{i,n}(t) \cdot P_i$ ) is to be summed from i=0 to i=n.

Taking the above figure as an example, assuming we want to calculate P(0.1), how to do it? It is expanded as follows:

Substitute t=0.1 to get:

Parametric representation of the curve

Here directly cites an article from a netizen (link)

Let's focus on the formula above.

As shown in the figure above, the straight line we are familiar with can be understood from another perspective: using t (i.e., the length of |AP| from the point P to the known point (x0,y0)), then point P can be determined through the above trigonometric functions.

More generally, it can be written as:

Here, P0 is the vector [x0,y0]and v is also a vector. When added together, P(t)is the vector [x,y].

Looking at the circle again:

As shown in the diagram, the circle can be viewed as having a known center, with any point on the circle being determined by the rotation angle and the radius. It can also be written as:

The parametric equations maintain geometric invariance and can represent shapes like circles (where one x corresponds to multiple y values).

De Casteljau

The De Casteljau algorithm is a method used in practical applications to evaluate and approximate Bézier curves for drawing and other operations. Compared to the previous definition-based evaluation method, it is faster and more stable, and closer to the characteristics of Bézier curves.

Here, we refer to two articles: link1 and link2

Firstly, the following is defined:

Look at the above β. It's a bit confusing with the superscripts and subscripts; you can use the following triangular recursion for understanding:

The red edges of the triangle in the above figure are the control points of the two segments divided by t0. To more vividly understand t0, P(t0) （i.e., $β0(n)\beta_0^{(n)}$ ）, the control points of the two curves, you can refer to the following figure:

The figure above demonstrates the relationships between various points when t=0.5.

From the perspective of "interpolation," the calculation process can also be understood as:

Finding the midpoints of each pair of adjacent control points (because t=0.5), that is, b01, b11, b21 (please forgive my notation; writing in LaTeX is too troublesome)
Find the midpoint b02 on b01−b11, and find the midpoint b12 on b11-b21
Find the midpoint b03 on b02−b12 In fact, the essence of the De Casteljau algorithm is interpolation and iteration.

Curve Drawing Based on De Casteljau

Currently, two methods are observed.

One method involves traversing t from 0 to 1 with small step increments（i.e. 0.01). Each time P(t) is sought, a recursive formula is used to determine $β0(n)\beta_0^{(n)}$ .

The other method involves seeking P(t=0.5), and then for the two divided curves, P(t=0.5) is sought respectively... This subdivision continues until the curve is approximated.

Implementation

It always feels unreal to just watch without practicing.

So I wrote my own implementation code for curve drawing and organized it into a toolkit: Compilelife's Toolkit

Corresponding core code is here

Painful Analyse Log ? Your Approach Might Be Wrong

compilelife — Sun, 28 Jul 2024 08:45:33 +0000

You've likely identified numerous bugs from various error logs, but have also been troubled countless times by lengthy and complex logs.

I also often suffer from the agony of log reviewing, typically due to:

Log files are so large that it's difficult to even open them.
The information within the log files is intricately intertwined, with the sequences of various modules being unclear.
The log are split into multiple parts, necessitating constant switching between them

Not only are the logs hard to stomach, but the tools for viewing them are also not user-friendly:

After searching for a keyword and jumping around a bit, I often forget what I was doing (Who am I, where am I, what am I doing?).
When I want to filter logs by a certain keyword, some tools don't even support it.
Just when I've got my analysis all figured out, I forget how to start explaining it as soon as someone else comes over.

These issues can be divided into two categories: first, the tools themselves are problematic, with insufficient functionality; second, there is a lack of systematic methods for troubleshooting issues from logs.

For the former, what we need are professional log viewing tools, not just editors; for the latter, I have summarized some methodologies that I can share.

Visualization of Thought Process

The general steps for troubleshooting logs are: Understand the problem => Locate the error => Examine the context => Infer the cause of the error.

In this process, if you consider the logs as a one-dimensional line, then reviewing the logs is like jumping back and forth along the line, gathering information, and drawing conclusions.

The problems mentioned above, such as forgetting where you've read in the logs, or not knowing where to start when explaining to others, are due to not recording your browsing path, gathered information, summarized doubts, and tentative hypotheses in real-time.

What is the most suitable way to record and visualize these elements? I believe it is the "Timeline."

How do we use a timeline? Imagine you are organizing historical events. When you find something valuable in the logs (a significant event), you place that spot (log line) into the timeline, becoming a "node."

At first, the timeline is just a bookmark bar, helping us record location information. For example, where the error occurred, what was happening at a certain time, what happened before or after something else, etc.

Next, we start to combine the logs with the timeline, gradually discovering some doubts. If a place seems suspicious, we add a comment to that node; if a value printed seems wrong, we color that node yellow... This is very similar to a mind map.

The process above, which seems to be centered around organizing log events along the "timeline," is essentially an examination of our own thought process (identifying suspicious points, connecting before and after, and arguing). In other words, at this point, the "timeline" is already playing the role of visualizing our thought process.

Using visualization brings another benefit: we can send this organized timeline to workmate to explain our log analysis process. Isn't this more intuitive than just using plain text descriptions?

Primary + Auxiliary

The "timeline" mentioned above serves as a consistent place to record, edit, and visualize thoughts without being disturbed or interrupted by other information.

While the timeline helps us maintain our thought process along the dimension of time, the "filter window" helps us keep our thought process on track along the dimension of information.

In log troubleshooting, it's common to filter logs containing a specific keyword to focus on a particular topic (information filtering). But is filtering enough?

Filtering can lead to the loss of information. What we need to understand is what's happening in the entire log with the filtered log entries, where they are distributed, what the context (other modules) is doing, and how they relate to the nodes (events) in the timeline before and after...

In other words, the auxiliary information filtered by keywords, in addition to its own informational value, also needs to be extracted against the main log to obtain more information. In other words, it is both parallel and intertwined.

So, How to reasonably resolve this contradiction?

There are three major areas in the image above: the main window in the upper left, the filter pane in the lower left, and the timeline on the right.

I define the information filtered by keywords as auxiliary information, placed in the filter pane, and the main window displays the complete log to achieve parallel viewing.

At the same time, using 'time' as the 'link' to connect the 'main window', 'filter pane', and 'timeline', no matter which event is clicked in any of the windows, the other two windows will immediately locate to the corresponding position, thus achieving the interweaving of information.

TAG

Viewing logs is not something that can be accomplished by just searching for one or two keywords (what can be done by searching for one or two keywords is merely a cursory glance), but it involves many. Therefore, it would be best to record the searched keywords, and ideally, mark them with different colors.

So, I also designed a TAG bar to record the currently highlighted keywords.

Segmented log

Of course, we won't forget about segmented logs. The most direct and intuitive way to deal with them is to 'reassemble' them! By viewing them in memory in a 'continuous' manner, we can forget that they are segmented during analysis and operate seamlessly as if analyzing a single 'large log'.

Of course, different log segmentation rules will produce different segmentation reassembly rules. This point must not be overlooked in tool support.

In order to reviewing logs "happily", functions such as locating to a specific line, go forward/backward, reverse search, font settings... and so on, cannot be lacking.

Since we have already explored certain experiences and methods in log analysis, and existing tools are not particularly convenient, of course I need to write one myself!

Please have a look at the log analysis tool I've created: "Loginsight" (Available on mac apple store).