Experimental Work

Compare the speed of numerical predicates (23 bit floating point numbers to make things realistic) - sphere vectors with GCD - hull - Johnathan Schewchuk's predicate - CGAL's predicates

Compare the memory management - simplex pool or (new) and (delete)

compare using point at infinity and far-away point.

Flip or no flip. Compare the # of deleted and constructed ridges (neighbor relations)

How much degeneracy do we get with small integer grid? analysis? experiments with 10bit integer grid in 4D.

Implement set vector and neighbor vector with compression to save memory.

Organize tess3, tess4 and Exact Delaunay. Ordering along Hilbert curve. ( should support tess3 streaming well).

-- YuanxinLiu - 28 Jul 2005

Discussion with Wenjie

Ingredients for wavelet to work

Basis selection

  • polynomial reproduction ( not so easy )
  • refinement ( easy. as long as the Michelli refinement formula is well defined )
  • vanishing moments (hard)

Rendering - refinement formula = subdivision formula?

-- YuanxinLiu - 04 Jun 2005

Point at infinity, finally found in the "negative" portion of the oriented projective space.

-- YuanxinLiu - 05 May 2005

SGP paper

Extend levelling to more bits and do scanned data. Interpolate some functions to measure how bad a bad triangulation is.

Has any of Jack's students implemented surface extraction?

Good streaming behavior

What I should do is to reorder the stream if there is a long prefix of finalized DTs with just a few stationary ones: just swap the last few finalized with the bad stationary ones and update neighboring relations.

Rounding
What's the effect of rounding for a single polygon ( as opposed to arrangement) in the plane? What happens in 3D? It will be nice if we can still get homeomorphic surfaces.

-- YuanxinLiu - 20 Apr

Two streams or better ordering of points?

The streaming k-Vor has a defeciency. A Delaunay is finalized when all of its neighbors are behind the sweep line (hence will stay). Whenever we have a prefix of finalized Delaunay of length greater than the block size, we write the prefix to disk. But since some Delaunays have infinite neighbors, they are never finalized and the stream is "stuck". There are two ways to "unstuck" the stream:

  • Use two streams: a Delaunay that are suspected of being "bad" are put on another stream. Hopefully there are few bad ones. and we need a merge in the end.

  • Do (order k)-convex hull computation first so that we don't have to deal with the infinite ones.

-- YuanxinLiu - 18 Apr

We can introduce discontinuity into natural neighbor interpolation as follow:

  1. Make the discontinuity lines into "slits" so that the domain to tessellate is a polygon w/ holes , in general.
  2. Compute the constrained Delaunay.
  3. For each site, define its Vornoi polygon as the intersection of the bisectors with its (triangulation) neighbors. If we are not working with the contrained Delaunay. These polygons form a cell complex, but in this case they might overlap, which will introduce discontinuity in the interpolation.
  4. Natural neighbor interpolation can be defined as before. That is, the weight of a site is determined by the area its polygon "loses" after a new site is inserted.

Another question is how we can introduce discontinuity in the direvative. This should be hard to do for interpolation scheme like natural neighbor, which does not ever look at direvative during the interpolation process.

Cleaned up code in ktess.cpp.

-- YuanxinLiu - 14 Apr 2005 Reading on wavelets.

An introduction to wavelets through linear algebra by Michael Frazier is an excellent for someone with someone with an undegraduate math major background: the main vocubulary are tightly constrained in elementary linear algebra and real analysis.

Questions that I wish to answer:

  • Where does Charles Chui's stuff fit? First generation? Second generation?
  • For the second generation wavelets, i.e., the ones gotten from lifting/subdivison scheme of Sweldens and Schroder, one designs filters and then look at scaling functions. (?) What properties do these scaling functions (not) have? It seems classic wavelets stuff approaches from the opposite directions basis functions -> filters.
  • Does it make sense to "decouple" the compression from the interpolation? i,e. Use waterever filter that is good at "prediction" of future data samples. But use whatever surface is best for interpolation.

-- YuanxinLiu - 13 Apr 2005

A synoposis of the state of streamVor

The previous question about how to output the neighbor relations actually reveals that two buffers are needed for streaming k-Voronoi: one that maintains the set of Delaunays needed in RAM, the other maintains a set of (finalized) Delaunays in the stream that neighbor those still in RAM. Another way to see this is that whenever a Delaunay D is written to disk, it has to be finalized twice. The first time D is finalized from RAM to the stream buffer because it is no longer needed for the construction; the second time D is finalized from the stream buffer to disk because all its neighbors are finalized from RAM to stream so their addresses in the stream are known to D.

The implementation of of the above ideas is complete. The streaming Voronoi program outputs correctly a file with all Delaunays with neighboring relations.

Todo

streamVor

  • implement sorted list of live spheres
  • Reimplement walk.

streamSSpline

  • (in RAM) experiment with different interpolation schemes: select a subset of samples that are good for interpolation; average the valies of samples; least square interpolation.

-- YuanxinLiu - 11 Apr 2005

Finished an implementation of streaming k-Voronoi.

I ran streaming k-vor on 10k random points. The max amount memory used in streaming is about 1/17 of the memory size of the output without streaming.

Todo:

  • how do we output the neighbor relations
  • implement sorted list of live spheres
  • Reimplement walk.

-- YuanxinLiu - 04 Apr 2005

Using Hollig's formula for derivative, we have the following corollary: In 1D, the maximum of a K-Degree basis is located at the intersection of its two K-1-degree children basis. Since Hollig's formula is not closed form, we don't have a formula. But it gives a nice geometric intution which seems to suggest there is not going to be any simple formula for the maximal location, since it is the intersection of B-splines.

In 2D, the picture breaks down. It is the solution of

 a1*M1 + a2*M2 = M3
 b1*M1 + b2*M2 = M3
, where M1, M2 and M3 are the three lower degree simplex splines and a1, a2, b1 and b2 are gotten from manipulating the coeffecients of Hollig's formula.

At least the dimension makes sense: M3 interested with the surface from the first equation gives us a curve on M3. M3 intersected with the surface from the second equation gives us another curve on M3. The intersection of these curves is where the maximal is located.

-- YuanxinLiu - 16 Mar 2005

The maximal of a quadratic b-spline basis over (0, a, b, 1) is located at b/(1-a+b).

For 2D, we can check that any of the three configurations of five knots happen to only have one piece that is not on the boundary. Since quadratic function only have one mode, this piece must be the one with max, since other pieces all have min. (maybe the weighted convolution version will help?)

The convolution interpretation of B-spline doesn't help. Since the first degree b-spline is gotten by convolving a box with another box and is symmetrical. There is no way the maximal can be located at non-zero location. We can actually convince our selves that this can't be easily fixed up : start with a isymmetrical hat and convulve with a box. This will never produce the degenerate shape produced by (0, a, a + epsilon, 1).

-- YuanxinLiu - 15 Mar 2005

Revision: r1.1 - 28 Jul 2005 - 22:04 - Main.guest
Main > TWikiUsers > YuanxinLiu > ResearchDiary
Copyright © 1999-2024 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback