From 0558b53493a77bae44831cf87bb0f59359828ef5 Mon Sep 17 00:00:00 2001 From: bubnikv Date: Wed, 19 Sep 2018 11:02:24 +0200 Subject: WIP: Moved sources int src/, separated most of the source code from Perl. The XS was left only for the unit / integration tests, and it links libslic3r only. No wxWidgets are allowed to be used from Perl starting from now. --- src/qhull/html/qh-eg.htm | 693 +++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 693 insertions(+) create mode 100644 src/qhull/html/qh-eg.htm (limited to 'src/qhull/html/qh-eg.htm') diff --git a/src/qhull/html/qh-eg.htm b/src/qhull/html/qh-eg.htm new file mode 100644 index 000000000..a08f0d13f --- /dev/null +++ b/src/qhull/html/qh-eg.htm @@ -0,0 +1,693 @@ + + + + +Examples of Qhull + + + + +

Up: Home +page for Qhull
+Up: Qhull manual: Table of Contents
+To: Programs +• Options +• Output +• Formats +• Geomview +• Print +• Qhull +• Precision +• Trace +• Functions
+To: Qhull examples: Table of Contents (please wait +while loading)
+ +

+ +

[halfspace] Examples of Qhull

+ +

This section of the Qhull manual will introduce you to Qhull +and its options. Each example is a file for viewing with Geomview. You will need to +use a Unix computer with a copy of Geomview. +

+If you are not running Unix, you can view pictures +for some of the examples. To understand Qhull without Geomview, try the +examples in Programs and +Programs/input. You can also try small +examples that you compute by hand. Use rbox +to generate examples. +

+To generate the Geomview examples, execute the shell script eg/q_eg. +It uses rbox. The shell script eg/q_egtest generates +test examples, and eg/q_test exercises the code. If you +find yourself viewing the inside of a 3-d example, use Geomview's +normalization option on the 'obscure' menu.

+ +

Copyright © 1995-2015 C.B. Barber

+ +
+ +

»Qhull examples: Table of +Contents

+ + + +
+ + +
+ +

»2-d and 3-d examples

+ +

»rbox c D3 | qconvex G +>eg.01.cube

+ +

The first example is a cube in 3-d. The color of each facet +indicates its normal. For example, normal [0,0,1] along the Z +axis is (r=0.5, g=0.5, b=1.0). With the 'Dn' option in rbox, +you can generate hypercubes in any dimension. Above 7-d the +number of intermediate facets grows rapidly. Use 'TFn' to track qconvex's progress. Note +that each facet is a square that qconvex merged from coplanar +triangles.

+ +

»rbox c d G3.0 | qconvex G +>eg.02.diamond.cube

+ +

The second example is a cube plus a diamond ('d') scaled by rbox's +'G' option. In higher dimensions, diamonds are much simpler than +hypercubes.

+ +

»rbox s 100 D3 | qconvex G +>eg.03.sphere

+ +

The rbox s option generates random points and +projects them to the d-sphere. All points should be on the convex +hull. Notice that random points look more clustered than you +might expect. You can get a smoother distribution by merging +facets and printing the vertices, e.g., rbox 1000 s | qconvex +A-0.95 p | qconvex G >eg.99.

+ +

»rbox s 100 D2 | qconvex G +>eg.04.circle

+ +

In 2-d, there are many ways to generate a convex hull. One of +the earliest algorithms, and one of the fastest, is the 2-d +Quickhull algorithm [c.f., Preparata & Shamos '85]. It was the model for +Qhull.

+ +

»rbox 10 l | qconvex G +>eg.05.spiral

+ +

One rotation of a spiral.

+ +

»rbox 1000 D2 | qconvex C-0.03 +Qc Gapcv >eg.06.merge.square

+ +

This demonstrates how Qhull handles precision errors. Option 'C-0.03' requires a clearly convex angle +between adjacent facets. Otherwise, Qhull merges the facets.

+ +

This is the convex hull of random points in a square. The +facets have thickness because they must be outside all points and +must include their vertices. The colored lines represent the +original points and the spheres represent the vertices. Floating +in the middle of each facet is the centrum. Each centrum is at +least 0.03 below the planes of its neighbors. This guarantees +that the facets are convex.

+ +

»rbox 1000 D3 | qconvex G +>eg.07.box

+ +

Here's the same distribution but in 3-d with Qhull handling +machine roundoff errors. Note the large number of facets.

+ +

»rbox c G0.4 s 500 | qconvex G +>eg.08a.cube.sphere

+ +

The sphere is just barely poking out of the cube. Try the same +distribution with randomization turned on ('Qr'). This turns Qhull into a +randomized incremental algorithm. To compare Qhull and +randomization, look at the number of hyperplanes created and the +number of points partitioned. Don't compare CPU times since Qhull's +implementation of randomization is inefficient. The number of +hyperplanes and partitionings indicate the dominant costs for +Qhull. With randomization, you'll notice that the number of +facets created is larger than before. This is especially true as +you increase the number of points. It is because the randomized +algorithm builds most of the sphere before it adds the cube's +vertices.

+ +

»rbox d G0.6 s 500 | qconvex G +>eg.08b.diamond.sphere

+ +

This is a combination of the diamond distribution and the +sphere.

+ +

»rbox 100 L3 G0.5 s | qconvex +G >eg.09.lens

+ +

Each half of the lens distribution lies on a sphere of radius +three. A directed search for the furthest facet below a point +(e.g., qh_findbest in geom.c) may fail if started from +an arbitrary facet. For example, if the first facet is on the +opposite side of the lens, a directed search will report that the +point is inside the convex hull even though it is outside. This +problem occurs whenever the curvature of the convex hull is less +than a sphere centered at the test point.

+ +

To prevent this problem, Qhull does not use directed search +all the time. When Qhull processes a point on the edge of the +lens, it partitions the remaining points with an exhaustive +search instead of a directed search (see qh_findbestnew in geom2.c). +

+ +

»How Qhull adds a point

+ +

»rbox 100 s P0.5,0.5,0.5 | +qconvex Ga QG0 >eg.10a.sphere.visible

+ +

The next 4 examples show how Qhull adds a point. The point +[0.5,0.5,0.5] is at one corner of the bounding box. Qhull adds a +point using the beneath-beyond algorithm. First Qhull finds all +of the facets that are visible from the point. Qhull will replace +these facets with new facets.

+ +

»rbox 100 s +P0.5,0.5,0.5|qconvex Ga QG-0 >eg.10b.sphere.beyond

+ +

These are the facets that are not visible from the point. +Qhull will keep these facets.

+ +

»rbox 100 s P0.5,0.5,0.5 | +qconvex PG Ga QG0 >eg.10c.sphere.horizon

+ +

These facets are the horizon facets; they border the visible +facets. The inside edges are the horizon ridges. Each horizon +ridge will form the base for a new facet.

+ +

»rbox 100 s P0.5,0.5,0.5 | +qconvex Ga QV0 PgG >eg.10d.sphere.cone

+ +

This is the cone of points from the new point to the horizon +facets. Try combining this image with eg.10c.sphere.horizon +and eg.10a.sphere.visible. +

+ +

»rbox 100 s P0.5,0.5,0.5 | +qconvex Ga >eg.10e.sphere.new

+ +

This is the convex hull after [0.5,0.5,0.5] has been added. +Note that in actual practice, the above sequence would never +happen. Unlike the randomized algorithms, Qhull always processes +a point that is furthest in an outside set. A point like +[0.5,0.5,0.5] would be one of the first points processed.

+ +

»rbox 100 s P0.5,0.5,0.5 | +qhull Ga QV0g Q0 >eg.14.sphere.corner

+ +

The 'QVn', 'QGn ' and 'Pdk' +options define good facets for Qhull. In this case 'QV0' defines the 0'th point +[0.5,0.5,0.5] as the good vertex, and 'Qg' +tells Qhull to only build facets that might be part of a good +facet. This technique reduces output size in low dimensions. It +does not work with facet merging.

+ +

»Triangulated output or joggled input

+ +

»rbox 500 W0 | qconvex QR0 Qc Gvp >eg.15a.surface

+ +

This is the convex hull of 500 points on the surface of +a cube. Note the large, non-simplicial facet for each face. +Qhull merges non-convex facets. + +

If the facets were not merged, Qhull +would report precision problems. For example, turn off facet merging +with option 'Q0'. Qhull may report concave +facets, flipped facets, or other precision errors: +

+rbox 500 W0 | qhull QR0 Q0 +
+ +

+

»rbox 500 W0 | qconvex QR0 Qt Qc Gvp >eg.15b.triangle

+ +

Like the previous examples, this is the convex hull of 500 points on the +surface of a cube. Option 'Qt' triangulates the +non-simplicial facets. Triangulated output is +particularly helpful for Delaunay triangulations. + +

+

»rbox 500 W0 | qconvex QR0 QJ5e-2 Qc Gvp >eg.15c.joggle

+ +

This is the convex hull of 500 joggled points on the surface of +a cube. The option 'QJ5e-2' +sets a very large joggle to make the effect visible. Notice +that all of the facets are triangles. If you rotate the cube, +you'll see red-yellow lines for coplanar points. +

+With option 'QJ', Qhull joggles the +input to avoid precision problems. It adds a small random number +to each input coordinate. If a precision +error occurs, it increases the joggle and tries again. It repeats +this process until no precision problems occur. +

+Joggled input is a simple solution to precision problems in +computational geometry. Qhull can also merge facets to handle +precision problems. See Merged facets or joggled input. + +

»Delaunay and Voronoi diagrams

+ +

»qdelaunay Qt +<eg.data.17 GnraD2 >eg.17a.delaunay.2

+ +

+The input file, eg.data.17, consists of a square, 15 random +points within the outside half of the square, and 6 co-circular +points centered on the square. + +

The Delaunay triangulation is the triangulation with empty +circumcircles. The input for this example is unusual because it +includes six co-circular points. Every triangular subset of these +points has the same circumcircle. Option 'Qt' +triangulates the co-circular facet.

+ +

»qdelaunay <eg.data.17 +GnraD2 >eg.17b.delaunay.2i

+ +

This is the same example without triangulated output ('Qt'). qdelaunay +merges the non-unique Delaunay triangles into a hexagon.

+ +

»qdelaunay <eg.data.17 +Ga >eg.17c.delaunay.2-3

+ +

This is how Qhull generated both diagrams. Use Geomview's +'obscure' menu to turn off normalization, and Geomview's +'cameras' menu to turn off perspective. Then load this object +with one of the previous diagrams.

+ +

The points are lifted to a paraboloid by summing the squares +of each coordinate. These are the light blue points. Then the +convex hull is taken. That's what you see here. If you look up +the Z-axis, you'll see that points and edges coincide.

+ +

»qvoronoi QJ +<eg.data.17 Gna >eg.17d.voronoi.2

+ +

The Voronoi diagram is the dual of the Delaunay triangulation. +Here you see the original sites and the Voronoi vertices. +Notice the each +vertex is equidistant from three sites. The edges indicate the +Voronoi region for a site. Qhull does not draw the unbounded +edges. Instead, it draws extra edges to close the unbounded +Voronoi regions. You may find it helpful to enclose the input +points in a square. You can compute the unbounded +rays from option 'Fo'. +

+ +

Instead +of triangulated output ('Qt'), this +example uses joggled input ('QJ'). +Normally, you should use neither 'QJ' nor 'Qt' for Voronoi diagrams. + +

»qvoronoi <eg.data.17 +Gna >eg.17e.voronoi.2i

+ +

This looks the same as the previous diagrams, but take a look +at the data. Run 'qvoronoi p <eg/eg.data.17'. This prints +the Voronoi vertices. + +

With 'QJ', there are four nearly identical Voronoi vertices +within 10^-11 of the origin. Option 'QJ' joggled the input. After the joggle, +the cocircular +input sites are no longer cocircular. The corresponding Voronoi vertices are +similar but not identical. + +

This example does not use options 'Qt' or 'QJ'. The cocircular +input sites define one Voronoi vertex near the origin.

+ +

Option 'Qt' would triangulate the corresponding Delaunay region into +four triangles. Each triangle is assigned the same Voronoi vertex.

+ +

» rbox c G0.1 d | +qdelaunay Gt Qz <eg.17f.delaunay.3

+ +

This is the 3-d Delaunay triangulation of a small cube inside +a prism. Since the outside ridges are transparent, it shows the +interior of the outermost facets. If you slice open the +triangulation with Geomview's ginsu, you will see that the innermost +facet is a cube. Note the use of 'Qz' +to add a point "at infinity". This avoids a degenerate +input due to cospherical points.

+ +

»rbox 10 D2 d | qdelaunay +Qu G >eg.18a.furthest.2-3

+ +

The furthest-site Voronoi diagram contains Voronoi regions for +points that are furthest from an input site. It is the +dual of the furthest-site Delaunay triangulation. You can +determine the furthest-site Delaunay triangulation from the +convex hull of the lifted points (eg.17c.delaunay.2-3). +The upper convex hull (blue) generates the furthest-site Delaunay +triangulation.

+ +

»rbox 10 D2 d | qdelaunay +Qu Pd2 G >eg.18b.furthest-up.2-3

+ +

This is the upper convex hull of the preceding example. The +furthest-site Delaunay triangulation is the projection of the +upper convex hull back to the input points. The furthest-site +Voronoi vertices are the circumcenters of the furthest-site +Delaunay triangles.

+ +

»rbox 10 D2 d | qvoronoi +Qu Gv >eg.18c.furthest.2

+ +

This shows an incomplete furthest-site Voronoi diagram. It +only shows regions with more than two vertices. The regions are +artificially truncated. The actual regions are unbounded. You can +print the regions' vertices with 'qvoronoi Qu o'.

+ +

Use Geomview's 'obscure' menu to turn off normalization, and +Geomview's 'cameras' menu to turn off perspective. Then load this +with the upper convex hull.

+ +

»rbox 10 D3 | qvoronoi QV5 +p | qconvex G >eg.19.voronoi.region.3

+ +

This shows the Voronoi region for input site 5 of a 3-d +Voronoi diagram.

+ +

»Facet merging for imprecision

+ +

»rbox r s 20 Z1 G0.2 | +qconvex G >eg.20.cone

+ +

There are two things unusual about this cone. +One is the large flat disk at one end and the other is the +rectangles about the middle. That's how the points were +generated, and if those points were exact, this is the correct +hull. But rbox used floating point arithmetic to +generate the data. So the precise convex hull should have been +triangles instead of rectangles. By requiring convexity, Qhull +has recovered the original design.

+ +

»rbox 200 s | qhull Q0 +R0.01 Gav Po >eg.21a.roundoff.errors

+ +

This is the convex hull of 200 cospherical points with +precision errors ignored ('Q0'). To +demonstrate the effect of roundoff error, we've added a random +perturbation ('R0.01') to every +distance and hyperplane calculation. Qhull, like all other convex +hull algorithms with floating point arithmetic, makes +inconsistent decisions and generates wildly wrong results. In +this case, one or more facets are flipped over. These facets have +the wrong color. You can also turn on 'normals' in Geomview's +appearances menu and turn off 'facing normals'. There should be +some white lines pointing in the wrong direction. These +correspond to flipped facets.

+ +

Different machines may not produce this picture. If your +machine generated a long error message, decrease the number of +points or the random perturbation ('R0.01'). +If it did not report flipped facets, increase the number of +points or perturbation.

+ +

»rbox 200 s | qconvex Qc +R0.01 Gpav >eg.21b.roundoff.fixed

+ +

Qhull handles the random perturbations and returns an +imprecise sphere. +In this case, the output is a weak approximation to the points. +This is because a random perturbation of 'R0.01 ' is equivalent to losing all but +1.8 digits of precision. The outer planes float above the points +because Qhull needs to allow for the maximum roundoff error.

+

+If you start with a smaller random perturbation, you +can use joggle ('QJn') to avoid +precision problems. You need to set n significantly +larger than the random perturbation. For example, try +'rbox 200 s | qconvex Qc R1e-4 QJ1e-1'. + +

»rbox 1000 s| qconvex C0.01 +Qc Gcrp >eg.22a.merge.sphere.01

+ +

»rbox 1000 s| qconvex +C-0.01 Qc Gcrp >eg.22b.merge.sphere.-01

+ +

»rbox 1000 s| qconvex C0.05 +Qc Gcrpv >eg.22c.merge.sphere.05

+ +

»rbox 1000 s| qconvex +C-0.05 Qc Gcrpv >eg.22d.merge.sphere.-05

+ +

The next four examples compare post-merging and pre-merging ('Cn' vs. 'C-n'). +Qhull uses '-' as a flag to indicate pre-merging.

+ +

Post-merging happens after the convex hull is built. During +post-merging, Qhull repeatedly merges an independent set of +non-convex facets. For a given set of parameters, the result is +about as good as one can hope for.

+ +

Pre-merging does the same thing as post-merging, except that +it happens after adding each point to the convex hull. With +pre-merging, Qhull guarantees a convex hull, but the facets are +wider than those from post-merging. If a pre-merge option is not +specified, Qhull handles machine round-off errors.

+ +

You may see coplanar points appearing slightly outside +the facets of the last example. This is becomes Geomview moves +line segments forward toward the viewer. You can avoid the +effect by setting 'lines closer' to '0' in Geomview's camera menu. + +

»rbox 1000 | qconvex s +Gcprvah C0.1 Qc >eg.23.merge.cube

+ +

Here's the 3-d imprecise cube with all of the Geomview +options. There's spheres for the vertices, radii for the coplanar +points, dots for the interior points, hyperplane intersections, +centrums, and inner and outer planes. The radii are shorter than +the spheres because this uses post-merging ('C0.1') +instead of pre-merging. + +

»4-d objects

+ +

With Qhull and Geomview you can develop an intuitive sense of +4-d surfaces. When you get into trouble, think of viewing the +surface of a 3-d sphere in a 2-d plane.

+ +

»rbox 5000 D4 | qconvex s GD0v +Pd0:0.5 C-0.02 C0.1 >eg.24.merge.cube.4d-in-3d

+ +

Here's one facet of the imprecise cube in 4-d. It's projected +into 3-d (the 'GDn' option drops +dimension n). Each ridge consists of two triangles between this +facet and the neighboring facet. In this case, Geomview displays +the topological ridges, i.e., as triangles between three +vertices. That is why the cube looks lopsided.

+ +

»rbox 5000 D4 | qconvex s +C-0.02 C0.1 Gh >eg.30.4d.merge.cube

+ +

Here +is the equivalent in 4-d of the imprecise square +and imprecise cube. It's the imprecise convex +hull of 5000 random points in a hypercube. It's a full 4-d object +so Geomview's ginsu does not work. If you view it in +Geomview, you'll be inside the hypercube. To view 4-d objects +directly, either load the 4dview module or the ndview +module. For 4dview, you must have started Geomview +in the same directory as the object. For ndview, +initialize a set of windows with the prefab menu, and load the +object through Geomview. The 4dview module includes an +option for slicing along any hyperplane. If you do this in the x, +y, or z plane, you'll see the inside of a hypercube.

+ +

The 'Gh' option prints the +geometric intersections between adjacent facets. Note the strong +convexity constraint for post-merging ('C0.1'). +It deletes the small facets.

+ +

»rbox 20 D3 | qdelaunay G +>eg.31.4d.delaunay

+ +

The Delaunay triangulation of 3-d sites corresponds to a 4-d +convex hull. You can't see 4-d directly but each facet is a 3-d +object that you can project to 3-d. This is exactly the same as +projecting a 2-d facet of a soccer ball onto a plane.

+ +

Here we see all of the facets together. You can use Geomview's +ndview to look at the object from several directions. +Try turning on edges in the appearance menu. You'll notice that +some edges seem to disappear. That's because the object is +actually two sets of overlapping facets.

+ +

You can slice the object apart using Geomview's 4dview. +With 4dview, try slicing along the w axis to get a +single set of facets and then slice along the x axis to look +inside. Another interesting picture is to slice away the equator +in the w dimension.

+ +

»rbox 30 s D4 | qconvex s G +Pd0d1d2D3

+ +

This is the positive octant of the convex hull of 30 4-d +points. When looking at 4-d, it's easier to look at just a few +facets at once. If you picked a facet that was directly above +you, then that facet looks exactly the same in 3-d as it looks in +4-d. If you pick several facets, then you need to imagine that +the space of a facet is rotated relative to its neighbors. Try +Geomview's ndview on this example.

+ +

»Halfspace intersections

+ +

»rbox 10 r s Z1 G0.3 | +qconvex G >eg.33a.cone

+ +

»rbox 10 r s Z1 G0.3 | +qconvex FV n | qhalf G >eg.33b.cone.dual

+ +

»rbox 10 r s Z1 G0.3 | +qconvex FV n | qhalf Fp | qconvex G >eg.33c.cone.halfspace

+ +

These examples illustrate halfspace intersection. The first +picture is the convex hull of two 20-gons plus an apex. The +second picture is the dual of the first. Try loading both +at once. Each vertex of the second picture corresponds to a facet +or halfspace of the first. The vertices with four edges +correspond to a facet with four neighbors. Similarly the facets +correspond to vertices. A facet's normal coefficients divided by +its negative offset is the vertice's coordinates. The coordinates +are the intersection of the original halfspaces.

+ +

The third picture shows how Qhull can go back and forth +between equivalent representations. It starts with a cone, +generates the halfspaces that define each facet of the cone, and +then intersects these halfspaces. Except for roundoff error, the +third picture is a duplicate of the first.

+ +
+ +

Up: Home +page for Qhull
+Up: Qhull manual: Table of Contents
+To: Programs +• Options +• Output +• Formats +• Geomview +• Print +• Qhull +• Precision +• Trace +• Functions
+To: Qhull examples: Table of Contents (please wait +while loading)
+ +

+ +

The Geometry Center +Home Page

+ +

Comments to: qhull@qhull.org +
+Created: Sept. 25, 1995 --- Last modified: see top

+ + -- cgit v1.2.3