ArticleslgStudy

computer science

Stencil jumping

Stencil jumping is a computer science topic covered in the lgStudy science library. This page brings together a partial reference excerpt, illustrations, worked examples, real-world applications and a short study plan, so you can understand Stencil jumping rather than just read about it. In short: Stencil jumping, at times called stencil walking, is an algorithm to locate the grid element enclosing a given point for any structured mesh. In simple words, given a point and a structured mesh, this algorithm will help locate the grid element that will enclose the given point.

Stencil jumping — main illustration
Stencil jumping — illustration

Key takeaways

  • Stencil jumping belongs to computer science; place it in that map before memorising details.
  • Learn the definition first, then one example that makes the definition concrete.
  • Connect Stencil jumping to a quantity you can measure, compute or draw — that is where exam questions come from.
  • Reproduce the core statement of Stencil jumping from memory before moving on to harder problems.

Reference excerpt

Stencil jumping, at times called stencil walking, is an algorithm to locate the grid element enclosing a given point for any structured mesh. In simple words, given a point and a structured mesh, this algorithm will help locate the grid element that will enclose the given point. This algorithm finds extensive use in Computational Fluid Dynamics (CFD) in terms of holecutting and interpolation when two meshes lie one inside the other. The other variations of the problem would be something like this: Given a place, at which latitude and longitude does it lie? The brute force algorithm would find the distance of the point from every mesh point and see which is smallest. Another approach would be to use a binary search algorithm which would yield a result comparable in speed to the stencil jumping algorithm. A combination of both the binary search and the stencil jumping algorithm will yield an optimum result in the minimum possible time.

The principle

Consider one grid element of a 2-dimensional mesh as shown, for simplicity and consider a point O inside. The vertices of the grid element are denoted by A, B, C and D and the vectors AB, BC, CD, DA, OA, OB, OC and OD are represented. The cross product of OA and AB will yield a vector perpendicular to the plane coming out of the screen. We say that the magnitude of the cross product is positive. It will be observed that the cross products of OB and BC, OC and CD; and OD and DA are all positive.

This is not the case when the point is outside. Here we see that not all the cross products are positive. This is the major testing criterion in the algorithm.

How does it move forward? The algorithm needs a guess grid element to start off. The grid element can be found by the location of one point say A. The other points can be automatically located by getting the subsequent points. The required cross products are then found in the order

OA × AB OB × BC OC × CD OD × DA Each of these cross products are checked one by one (in the order shown) on which becomes negative first. If OA × AB becomes negative first, the next guess should be one step ahead along DA. If OB × BC is negative first, move along AB by one step to find the next guess and so on. The algorithm will converge at the exact grid element where all the cross products are positive.

See also Five-point stencil

References

Rudy A. Johnson; Davy M. Belk (1993). "A MULTIGRID APPROACH TO EMBEDDED-GRID SOLVERS" (PDF (Fee required)). Technical Reports: USAF, Wright Lab., Eglin AFB. AIAA-1993-769. Retrieved 2007-05-31. E.G. Paterson; R.V. Wilson; F. Stern (May 1998). CFDSHIP-IOWA and Steady Flow RANS Simulation of DTMB Model 5415 (PDF). 1st Symposium on Marine Applications of CFD. p. 5. Archived from the original (PDF) on October 27, 2004. Retrieved 2007-05-31. Prewitt, Nathan C; Belk, Davy M; Shyy, Wei (2000). "Parallel computing of overset grids for aerodynamic problems with moving objects". Progress in Aerospace Sciences. 36 (2): 117. Bibcode:2000PrAeS..36..117P. doi:10.1016/S0376-0421(99)00013-5.

External links pegasus software

Illustrations

Stencil jumping: The point O lies outside the grid element ABCD.
The point O lies outside the grid element ABCD.

Worked examples

Example 1 — a first encounter with Stencil jumping

Start with the simplest possible case. Write down what Stencil jumping claims or describes in one sentence, then invent the smallest concrete situation in which that sentence is true. In computer science, the smallest case is usually a single object, a single equation or a single measurement. Check that every symbol or term in your sentence has a meaning in that case.

Example 2 — changing one variable

Take the situation from Example 1 and change exactly one quantity: double it, halve it, or set it to zero. Predict what should happen to Stencil jumping before you calculate. Comparing your prediction with the result is the fastest way to find out whether you understand the idea or only the words.

Example 3 — an exam-style question

Typical questions about Stencil jumping ask you to (a) state it precisely, (b) apply it to given data, and (c) explain a limitation. Practise writing all three answers in under five minutes; the third part is what separates a full-mark answer from an average one.

Applications of Stencil jumping

In research
Stencil jumping appears in computer science research whenever the underlying quantities have to be modelled precisely. Papers usually cite it as a starting assumption and then explore where it breaks down.
In technology and industry
Engineering practice reuses Stencil jumping in design rules, simulations and safety margins. Knowing the idea lets you read a specification sheet and understand why the numbers look the way they do.
In the classroom
Stencil jumping is common in secondary-school and first-year university syllabi. It links to neighbouring topics Geometric algorithms, so understanding it makes those chapters shorter.
In everyday life
Look for Stencil jumping outside the textbook — in sport, cooking, traffic, electronics or the sky above you. An example you found yourself is remembered far longer than one you were given.

Affiliate

Preply — study more efficiently by working with a personal tutor. 50% off.

How to study Stencil jumping in 20 minutes

  1. Read the reference excerpt below once, without taking notes.
  2. Close the page and write down what Stencil jumping means in your own words.
  3. Compare your version with the excerpt and mark what you missed.
  4. Work through the three examples above with pen and paper.
  5. Explain Stencil jumping out loud to somebody else — or to Teacher Smith in the lgStudy chat.

Frequently asked questions

What is Stencil jumping in simple terms?

Stencil jumping, at times called stencil walking, is an algorithm to locate the grid element enclosing a given point for any structured mesh. In simple words, given a point and a structured mesh, this algorithm will help locate the grid element that will enclose the given point.

Why does Stencil jumping matter?

Because it connects several computer science ideas at once: it gives you a definition you can apply, a quantity you can calculate, and a way to check whether a result is plausible.

How should I study Stencil jumping?

Read the excerpt, restate it from memory, then work through the examples and applications listed on this page. The five-step study plan above takes about twenty minutes.

What does this page cover?

It gives you a compact reference excerpt plus original lgStudy explanations, examples, applications and study material on Stencil jumping.

Tags

  • Geometric algorithms

Keep exploring