Home > Research

Contents:

Geometry Applications

1. Efficient Low-Level Operations

Several of these sections describe efficient low-level operations. Spending energy on simple problems may seem a waste of time, so why do I do it?

I like to do geometry as simply as possible. It is a joy to make a program simultaneously smaller, faster, and more robust. All implementations are tested on the largest datasets available.

As simple as possible (but no simpler) is a theme of these data structures and algorithms. Some of these techniques, such as the uniform grid, appear almost trivially simple (tho efficient implementation is more intricate than may be apparent). They are fast only for "expected data" and are totally uninteresting to the theoreticians since the worst case performance is abysmal. The only reasons for considering them are these.


  • The set of "expected data" is large, including every real data set that I've ever tried.
  • On such data, the constant factor for the time is quite small.
  • Being so simple, they are easy to implement, correctly, and optimize. This contrasts to some asymptotically efficient algorithms that are so complicated that they have not been implemented yet.
  • Being so simple, they are also parallelizable, should parallel machines become widely used again.
  • These heuristic methods occasionally solve problems that do not have worst-case efficient methods. One example is this. Consider a set of N red line segments and N blue ones. Assume that there are probably theta(N2) red-red intersections and also theta(N2) blue-blue intersections, but you do not know them. Assume that there are probably theta(1) red-blue intersections. The problem is to find these, in theta(N) time. The closest theoretical algorithm requires knowing the red-red intersections. However, this is easy with a uniform grid, w/o knowing the red-red intersections.
  • Nevertheless, there are interesting theoretical questions in analyzing when these heuristic methods succeed and fail.

2. PNPOLY (Point inclusion in polygon test)

Detailed information is here. This 8 line program, an update of what I wrote in 1970, tests if a point is inside a polygon in E2. It handles multiple components with nested holes and islands.

Compared to other routines attempting to test point inclusion, PNPOLY tends to be, simultaneously, smaller, faster, and more general.

2.1. FAQ

3. Geometric Operations on Millions of Objects

Slides of a good summary talk presented at Koc University, Istanbul, 16 July, Sabanci University, Istanbul, 20 July, Bilkent University, 26 July, and Middle Eastern Technical University, 27 July 2004.

4. XSECT2

This parallelizable algorithm finds all the intersections among a large number of small line segments in E2. The time to find all K intersections among N line segments is an expected (N+K), altho an adversary can choose input to raise that to N2. However no real data sets have exhibited that behavior. Data has been used from cartography, VLSI design, and nonuniform meshes.

This is a common operation in many higher-level operations such as boolean combinations. (1977)

5. Uniform Grids

Uniform grids are useful in many of the following applications. This idea is intended to be just sophisticated enough to solve the problem, without being so complicated that it is difficult to implement, including the messy special cases, and parallelize.

The concept, which is useful for culling pairs of objects that may intersect, is to overlay a uniform grid on the data. Then iterate over the elements, finding which grid cells each passes thru. Finally, iterate over the cells, comparing pairs of elements that pass thru the same cell. Implementing this properly requires some attention to detail. This method works well even when the data is unevenly distributed, where one's first impulse would be to use the, more complicated, quadtree. (1977)

5.1. Papers

6. NEARPT2 (Nearest Points in E2)

Nearpt2 is an online program to find nearest points in 2D. It reads a list of points, and preprocesses them into a data structure. Then it reads a list of query points, and, one by one, finds the closest fixed point to each query point.

Nearpt2 is very fast and very small. One test used vertices of two nonuniform meshes from Mark Shepherd. Processing the 10267 fixed points took about 0.01 CPU seconds on a 1600 MHz Pentium. Querying all 8005 test points took about 0.02 seconds.

Another test used 10,000,000 uniformly randomly generated fixed points and another 10,000,000 query points. The total preprocessing time was 12 CPU seconds on my laptop. The total query time was 65 seconds. The virtual memory was 460MB. The elapsed time including the main program's I/O was 415 seconds. (2003).

More info and the code is here.

7. NEARPT3 (Nearest Points in E3)

Nearpt3 is a pair of subroutines to find nearest points in E3. Preprocess takes a list of fixed points, and preprocesses them into a data structure. Query takes a query point, and returns the closest fixed point to it.

Nearpt3 is very fast, very small, and can process very nonhomogeneous data. The largest example run on a laptop computer was St Matthew from the Stanford Digital Michelangelo Project Archive, with 184,088,599 fixed points.

Preprocessing the David data set, with 28,158,109 fixed points, into a 7233 grid took 0.6 microseconds per fixed point. Each query required 6 microseconds. The platform was an IBM T43p laptop computer with a 2GHz Intel Pentium M processor and 2GB of memory.

More info is here. (12/7/2005)

8. Connect (find connected components)

Connect finds the connected components in a 3-D rectangular volume of binary voxels (the universe). For each component, Connect writes its volume, surface area, and voxels (grouped into runs). Connect can do both 6-connectivity and 26-connectivity.

Connect is very space- and time-efficient. E.g., processing one test volume of size 544x544x512, which has 151,519,232 voxels, about 1/2 empty, to find the 534,723 components, takes only 15 CPU seconds on a 1600MHz Pentium.

Processing a 2-D 18573x19110 image took 25 CPU seconds.

More details, and the code, are here. (1999)

8.1. Papers

9. Polygon and Polyhedron Data Structures

Localtopo is a new data structure for representing polygons and polyhedra by the location and purely local topology of each vertex. This contrasts with the complete topologies used in many CAD systems. My local data structure simplifies many operations, such as determination of the mass properties of boolean combinations of objects.

9.1. Papers & Talks

  • [localtopo] WR Franklin. Local topological properties of polyhedra. Sept 1992. Unpublished talk.

  • [f-ppcvn-87] WR Franklin. Polygon properties calculated from the vertex neighborhoods. In Proc. 3rd Annu. ACM Sympos. Comput. Geom., pages 110-118, 1987.

  • [f-rnrpp-83] WR Franklin. Rays - new representation for polygons and polyhedra. Computer Graphics and Image Processing, 22:327-338, 1983.

    10. Studies of Fundamentals

    E.g., an investigation into why raster graphics algorithms can be surprisingly counterintuitive and difficult.

    For example, consider finding the raster line segment between two points, such as with the Bresenham algorithm. Now, pick two points on the interior of that line and draw the new line segment between them. Probably the points of the new line segment will not be a subset of the points of the original line segment. This does not happen with ideal, vector, lines.

    The deep reason that raster graphics can be harder than vector graphics is that, in algebra, the integers are harder than the reals, not easier. E.g., first order logic over the reals with addition and multiplication is solvable. Not so over the integers.

    10.1. Papers

    11. Object Rotation

    11.1. Paper

    12. Linear Expected-Time Object-Space Hidden Surface Algorithm

    This relies on the useful property that, if the input faces are IID (independently and identically distributed), then the expected number of visible edge pieces is linear in the number of input edges, and I can find them all in expected linear time.

    This is remarkable since the total number of intersections of the projected input edges might be superlinear if the edges' lengths do not shrink fast enough. However, in that case, most of those intersections are hidden, and I can delete them in groups w/o spending even constant time per one. (1978)

    • 12.1. Papers

    13. Bottom-Up Octree Creation

    This is a better method for creating octrees by a bottom-up approach instead of using top-down subdivision. The idea is to intersect 1-D rays with the object, split the part of each ray that is inside the object into bintrees, group adjacent bintrees into quadtrees, then group adjacent quadtrees into octrees. This whole process has a systolic computation flavor. The advantage of this method is that it iss easier to intersect the object with a line than with a cube. (1985)

    13.1. Papers

    14. Overlaying 3D Triangulations

    This algorithm combines two different triangulations of the same 3D faceted object, to determine which pairs of tetrahedra overlap, and the intersection volumes. This is useful for interpolating data from one triangulation of an object to another. (1992)

    14.1. Paper

    15. UNION2, UNION3, and Boolean Operations and Their Mass Properties

    UNION2 is a demo program that finds the area and perimeter of the union of many random equal-sized squares. For example, for 100,000,000 squares with edge length 0.0006, the cpu execution time on a 1600 mhz pentium was only 11 minutes.

    UNION3 is a fast algorithm for computing the volume, area, and other mass properties, of the union of many polyhedra. UNION3 is well suited for parallel machines. A prototype implementation for identical random cubes has processed 20,000,000 polyhedra, containing half a billion subfacets, on a dual processor Pentium Xeon workstation in about one hour.

    UNION3 processes all the polyhedra in one pass instead of repeatedly combining them pair by pair. The first step finds the candidate output vertices. These are the 3-face intersections, edge-face intersections, and input vertices. Next, the candidates are culled by deleting those inside any polyhedron. The volume is the sum of a function of each survivor. There is no statistical sampling. Input degeneracies are processed with Simulation Of Simplicity. Since UNION3 never explicitly determines the output polyhedron, messy non-manifold cases become irrelevant. No complicated topological structures are computed. UNION3's simple flat data structures permit it to fork copies of itself to utilize multi-processor machines. The expected time is linear in the number of input, even when the number of intersections is superlinear.

    The principal data structure is a 3-D grid of uniform cells. Each cell records overlaps of itself with any edge, face, or polyhedron. Intersection tests are performed only between objects overlapping the same cell. However, if a cell is completely contained in some polyhedron, (covered), then no intersection tests are performed in it, since none of those intersections would be visible. Indeed, altho there may be a cubic number of intersections, all but a linear number occur in these covered cells, and are never computed. Therefore the final time is linear.

    15.1. Papers and Talks

    16. Misc Geometry Apps

    16.1. Papers

    17. General Papers & Surveys