Dream & Passion: CG

Showing posts with label CG. Show all posts

Friday, May 15, 2009

3D visualization

NZR

http://www.softserv-intl.us/

R-project

http://www.r-project.org/

Tuesday, March 10, 2009

Simple OpenGL Test Framework

http://www.codeproject.com/KB/openGL/OpenGLTestFrmwk.aspx

Monday, March 9, 2009

WPF & Ogre

http://www.codeproject.com/KB/WPF/OgreInTheWpf.aspx?display=PrintAll&fid=1526313&df=90&mpp=25&noise=3&sort=Position&view=Quick

An article about WPF & Ogre.

Blend the OGRE Graphics Engine into your WPF projects

Wednesday, March 4, 2009

One thing about Ogre Cameras that is different from what you may expect is that you should only be using one Camera at a time (for now). That is, we do not create a Camera for viewing one portion of a scene, a second camera for viewing another portion of the scene and then enabling or disabling cameras based on what portion of the scene we want to display. Instead the way to accomplish this is to create SceneNodes which act as "camera holders". These SceneNodes simply sit in the scene and point at what the Camera might want to look at. When it is time to display a portion of the Scene, the Camera simply attaches itself to the appropriate SceneNode.

Tuesday, March 3, 2009

Begin OGRE

After the SDK is installed, add "include" and "bin" directory of the SDK to the Visual Studio's VC++ Directories.

For each project, add "CEGUIBase.lib", "ode.lib", "OgreGUIRenderer.lib", "OgreMain.lib", "OIS.lib" and "ReferenceAppLayer_d.lib" to project's Link menu and Additional Dependencies. (Add all or add only the one you will use in your code.) Moreover, for the first 5 lib files, there is a version for debug: "CEGUIBase_d.lib", "OgreGUIRenderer_d.lib", "OgreMain_d.lib", "OIS_d.lib".

Missing a Configuration File or DLLs

If you try to launch your freshly built application but the program complains of missing DLLs or configuration files (*.cfg), then you probably did not copy them over from the OgreSDK folder. In Visual Studios, when you build your application in release mode, it puts the release executable in the [ProjectFolder]\bin\release folder, and the debug executable in the [ProjectFolder]\bin\debug folder. You must copy all the ".dll" and ".cfg" files over from the OgreSDK into the appropriate folders. That is, copy the files from [OgreSDK]\bin\release to [ProjectFolder]\bin\release and [OgreSDK]\bin\debug to [ProjectFolder]\bin\debug. You will also need to edit the resources.cfg file to point at the correct paths. See the next section for more information on this.

Also something in the "Resources.cfg" configuration file should be changed. However, I just copied the media folder to my project folder.

Cannot Launch the Application in Visual Studio

If you are using Visual Studio or Visual C++ to create the application and are having trouble launching it from the environment, the problem is most likely due to the debugger settings. If you press the play button (or go to the Start Debugging menu item) and you get an exception saying that a configuration file (*.cfg) cannot be found, then the Working Directory has probably not been set.

The exact instructions for fixing this will vary based on whichversion of Visual C++ you are using, so I cannot give you a direct walk through, but the basic steps should be the same. Right click on your project in the solution explorer (not the solution itself) and go to properties. Somewhere in the configuration properties should be options for "Debugging". In the debugging options there should be a field for "Working Directory". This should be set to the location that the executable file for your project is being placed.

If you are having trouble figuring out what to put there, try to mimic the "Command" field which should also be in the debugging options. For example, in Visual C++ 2003, the "Command" field should be something similar to "..\..\bin\$(ConfigurationName)\$(TargetFileName)". For the Working Directory, we need to remove the portion of the command which is the target file name (the executable). In this case, the working directory would be "..\..\bin\$(ConfigurationName)". The exact string you have to put there may vary based on your version of Visual C++ and on your build environment, so be sure to check what the Command field is before doing this. Be sure to change the Working Directory for both the Release and Debug configuration.

In Visual C++ 2005 it will probably be something different entirely. I've found the "..\..\bin\$(ConfigurationName)" directory a good thing to try first, if it still does not work you may have to play with it some, or consult some help from the Ogre forums.

The reason we have to do this is that Ogre expects certain files to be in the same directory as the executable, and without setting the working directory to be a directory with these files in it.

SceneNodes keep track of location and orientation for all of the objects attached to it. When you create an Entity, it is not rendered in the scene until you attach it to a SceneNode.In addition a SceneNode is not an object that is displayed on the screen. Only when you create a SceneNode and attach an Entity (or other object) to it is something actually displayed on the screen.

One major concept to note about SceneNodes is that a SceneNode's position is always relative to its parent SceneNode, and each SceneManager contains a root node to which all other SceneNodes are attached.

Sunday, March 1, 2009

Humanoid body model layout

Background

One of the most crucial pieces in the game is the media used to represent the players. This must allow for enough customization for the players to feel that they are in a living world, where they themselves are unique, as well as all of the other character. Therefore we need to have a common standard for all humanoid characters, so that they will all be able to represent the world in a correct way no matter what client they're used in.

Humanoid body model layout

An initial layout of the humanoid characters. The layout should be closely followed for female characters.

Clothing layout

The clothes parts needs to be synced with the body model. As an example, a long sleeved shirt will cover most of the arms, allowing the client to hide the "shoulder" and "elbow" parts (thus saving render ops), whereas a shirt sleeved shirt would require that either the "elbow" or also the "shoulder" part was visible.

cloak (over the head)
long sleeved shirt
shirt sleeved shirt
long pants
short pants
low shoes
tall shoes
apron
cape (this requies some physics simulation (mainly springs) which cal3d (used in Sear) has, though not Ember)

Armor

The armour should mostly be a suppliment to the clothing, i.e. it should be possible to wear a "shin guard" and a "long pants" at the same time. Some armour parts however takes precedence, for example when wearing a chain mail legging, all other pants that might be worn should automatically be hidden. An overview of the armour layout can be seen in the image to the left.

breast plate (large plate on the front of the torso)
shin guards
skirt guards
helmet (should this replace any hat or cloak worn? --Erik 00:38, 26 January 2007 (CET))
shoulder guards
chain mail (works like clothes)

Animations

The animations should correspond directly to actions in mason, in addition to the standard movement animations. The following is a compilation of the current status of the animations available for the humanoid character in Ember, and how they map against the server side actions.

Models

Animation name
Description
Ember name
Server actions
Status

Idle
The character is idle, breathes and perhaps shifts position, cracks the knuckles etc.. This would preferably be a couple of different animations that can be randomly played, to not make it too apparent that they're looping.
humanoid.skeleton: wf_humanoid-idle_*
Idle

Walk forwards
Simple forward walking animation
humanoid.skeleton: wf_humanoid_walk_Clip
Move forwards

Walk backwards
Simple backwards walking animation
Move backwards

Run forwards
Simple forward running animation
humanoid.skeleton: wf_humanoid_walk_Clip
Move forwards with greater speed

Sidestep
Simple side stepping walking animation
Move to the side

Swim
The character swims. For now we'll use the same animation for both idle and movement.
The character is placed in water

Pickup
The character picks something from the ground. The same animation can be used when the character drops something.
humanoid.skeleton: wf_humanoid-pick-up_Clip
Action: pickup, drop

General fidgeting
A general animation that can be used whenever there's no other animation to use for an action
humanoid.skeleton: wf_humanoid-fletching_Clip
Generic action

Chop
The character chops down a tree.
Action: chop

Punch
The character makes an offensive punch
humanoid.skeleton: wf_humanoid-offense_punch_Clip
Action: attack

Swing a sword
The character makes an offensive swing with a sword
Action: attack

Defend
The character defends against an offensive action
Action: defend

Eat
The character eats
Action: eat

Collapse
After being defeated in combat or starving to death, the character should collapse and end up in a collapsed state on the ground.
Action: collapse

Rise
After collapsing in combat, the character gets up again.
Action: ?

Dig
The character digs in the ground.
Action: dig

Delve
The character uses a pickaxe to delve.
Action: delve

Sow
The character uses a trowel to sow a seed in the ground.
Action: sow

From: http://wiki.worldforge.org/wiki/Human_model_layout

Thursday, February 26, 2009

Site: H-Anim

A site for humanoid animation. Specifications and so on.

http://h-anim.org/

Skeleton used in Humanoid Animation

To animate the humanoid character, a well defined skeleton is used. Following is the skeleton we studied and used in our work.

The skeleton(using maya joint):

The hierarchy of this skeleton is:

The hierarchy also can be seen from following selections in Maya:

The annotated reference skeleton model is:

The one we use is slightly different in the neck area:

Monday, February 23, 2009

Computational Geometry Code

This page lists "small" pieces of geometric software available on the Internet. Most of the software is available free of charge. Unless otherwise specified, C or C++ source code is available for all programs. Software libraries and collections and programs that can be run interactively over the web are listed on separate web pages.

Caveat Surfor! I can't make any claims about the usefulness or quality of the programs listed here. I don't have the time or equipment to try them all. If you have experience with any of these programs, either positive or negative, please tell me about it.

The programs on this page are divided into several categories, some of which are divided into further sub-categories. (Eventually, each category will get its own separate web page.) Each program is listed only once, but I've provided cross-links between overlapping categories, and I've tried to arrange similar categories near each other.

Each category also includes links to relevant pages in Nina Amenta's comprehensive Directory of Computational Geometry Software, which I strongly encourage you to visit!

Items marked [NEW!] have been recently added or modified.

Robust low-level primitives

Avoid roundoff and precision errors! Use this code instead of naïve floating point or integer arithmetic.

Relevant pages from DCGS:
- Numerical and algebraic computation
Ken Clarkson's Hull contains code to compute signs of determinants. See this paper for a description of his algorithms.
Sylvain Pion's Modular package, based on the algorithms in "Modular Arithmetic for Geometric Predicates" by Hervé Brönnimann, Ioannis Z. Emiris, Victor Pan and Sylvain Pion.
Adaptive precision floating point predicates used in Jonathan Shewchuk's Triangle package.
Libraries for affine arithmetic and interval arithmetic (the first requires the second) from Jorge Stolfi's software collection
Several algorithms to compute the exact sign of a deteminant (also here), collected by Mariette Yvinec. Part of the PRISME project at INRIA Sophia-Antipolis.
The LEDA libraries includes code for exact arbitrary-precision integer, rational, floating point, and "real" arithmetic.

Combinatorics and discrete math

LINK: A Software System for Discrete Mathematics under development at DIMACS
Ulli Hund's program om2ps for visualizing oriented matroids as arrangements of pseudospheres. Sample output is available.
Jorjeta Jetcheva's program to draw "clusters of stars", using an algorithm of Ileana Strienu (requires LEDA)
Komei Fukuda's Reverse Search mathematica package for enumerating triangulations and connected induced subgraphs. Requires Steve Skiena's Combinatorica package.

Geometric optimization

Relevant pages from DCGS:
- Linear programming, smallest enclosing ball and center point
Code by Ken Clarkson:
- Fixed-dimensional linear programming
- Approximate center points
From Graphics Utilities by David Eberly:
- Minimum enclosing circle
- Minimum enclosing sphere (3d only)
Mike Hohmeyer's implementation of Seidel's linear programming algorithm, courtesy of Seth Teller
ANN: Library for Approximate Nearest Neighbor Searching, by David Mount and Sunil Arya
Dave White's smallest enclosing ball software

Convex hulls and convex polyhedra

Most convex hull programs will also compute Voronoi diagrams and Delaunay triangulations. (Actually, all of them do, if you look at them the right way.)

Relevant pages from DCGS:

Low-dimensional convex hulls

Two-dimensional convex hulls by Ken Clarkson
From Graphics Utilities by David Eberly:
- 2d convex hulls: conhull2.h, conhull2.c
- 3d convex hulls: conhull3.h, conhull3.c
ZRAM, a library of parallel search algorithms and data structures by Ambros Marzetta and others, includes a parallel implementation of Avis and Fukuda's reverse search algorithm.
Geometric software by Darcy Quesnel:
- Randomized parallel 3D convex hull, with documentation
- 2D Delaunay triangulation, Voronoi diagram, and convex hull (requires LEDA)
Harald Rosenberger's implementation of the beneath-beyond method for 3- and 4-dimensional convex hulls, courtesy of Ernst Mücke's GeomDir.

Arbitrary-dimensional convex hulls

lrs 3.1: the first "official" distribution of David Avis' implementation of Avis and Fukuda's reverse search algorithm for vertex/facet enumeration. (This is an updated version of an earlier preliminary implementation.) An extensive user's guide is included.
Qhull by Brad Barber, David Dobkin, and Hannu Huhdanpaa
- Also available from this mirror site in Spain
- The latest version (2.5) was released February 4, 1998.
Primal-dual methods for vertex and facet enumeration by David Bremner, Komei Fukuda, and Ambros Marzetta
Hull: Arbitrary-dimensional convex hulls, Voronoi diagrams, Delaunay triangulations, and alpha shapes, by Ken Clarkson
PORTA, a collection of tools for analyzing polytopes and polyhedra, by Thomas Christof and Andreas Loebel, featured in Günter Ziegler's Lectures on Polytopes.
Computational geometry software by Ioannis Emiris: perturbed convex hulls in arbitrary dimensions, exact convex hulls in two and three dimensions, mixed volume in arbitrary dimensions, and mixed subdivisions in the plane.
Polytope software by Komei Fukuda
- cdd and cdd+: arbitrary-dimensional convex hulls using Motzkin's double description method
- A Mathematica package for Vertex enumeration of polytopes and arrangements
Kurt Mehlhorn's programs for generating higher dimensional convex hulls and Delaunay triangulations and checking geometric structures. (C++WEB output only)

Measure properties

Vinci (also here): a program for computing volumes of convex polytopes, presented as either the convex hull of a set of points, the intersection of a set of halfspaces, or both (with the vertex-facet incidence graph). Extensive online documentation and sample polytope files are available. Written by Benno Büeler, Andreas Enge, and Komei Fukuda.
Ehrhart, a program to count integer points in convex polyhedra and compute Ehrhart polynomials, by Philippe Claus, Vincent Loechner, and Doran Wilde.
Fast and accurate computation of polyhedral mass properties by Brian Mirtich, published in journal of graphics tools 1.2:31-50 (1996)

Boolean operations on polyhedra

Polymake, a general-purpose polytope and polyhedron manipulation tool by Ewgenij Gawrilow and Michael Joswig Requires either cdd+, lrs, or porta for some computations and geomview for visualization. [C++ and Perl]
Polylib, a library of polyhedral functions by Doran Wilde, includes code to compute convex hulls and perform boolean operations on unions of polytopes in any dimension.

Interesting and/or pathological polytope data

Examples of pathological polytopes collected by David Bremner. See "How Good are Convex Hull Algorithms?" by Avis, Bremner, and Seidel for details. (data only)
A collection of polytopes, mostly due to Günther Ziegler, from the polymake web site. (data only)

Miscellaneous

A Mathematica package for unfolding 3D polytopes ( README) by Komei Fukuda; see "Strange Unfoldings of Convex Polytopes" for details.
PUNTOS, a Maple package for computing triangulations of polytopes, regular triangulations of point sets, and their underlying oriented matroids, by Jesús de Loera
Convex polyhedron code from a collection of mathematical programming software at the Konrad-Zuse-Zentrum für Informationstechnik, Berlin.

Voronoi diagrams and Delaunay triangulations

See also the implementation page from Christopher Gold's site www.Voronoi.com.

Relevant pages from DCGS:

Voronoi diagrams and Delaunay triangulations of points

Many convex hull programs can also compute Voronoi diagrams and Delaunay triangulations.

2d and 3d Delaunay triangulations by Jean-Daniel Boissonnat, Olivier Devillers, Stefan Meiser, and Monique Teillaud, from the PRISME project at INRIA Sophia-Antipolis.
The Delaunay hieararchy, a data structure for 2d Delaunay triangulations that supports dynamic insertions (and deletions, but those aren't implemented), by Olivier Devillers, from the PRISME project at INRIA Sophia-Antipolis. (Solaris and SGI executables only)
Graphics utilities by David Eberly:
- 2d Delaunay triangulations: delaun2.c
- 3d Delaunay triangulations: delaun3.c
GAMBINI: a program for constructing multiplicatively weighted Voronoi diagrams for points in the plane, by Barry Boots. (Windows 3.1/95/NT executable only)
Ernst Mücke's Detri, from his GeomDir, robustly computes 3D Delaunay triangulations.
A simple divide-and-conquer Delaunay triangulation algorithm from Jorge Stolfi's software collection. Requires Stolfi'squad edge data structure library.
Software by John Sullivan includes code to compute either standard Voronoi diagrams in Euclidean 3-space or periodic Voronoi diagrams in the 3-torus.
Dave Watson's incremental convex hull/Delaunay triangulation program nnsort.c and a description of the algorithm
Roman Waupotitsch's MinMaxer generates Delaunay, regular, and various other triangulations of two-dimensional point sets.
Software on the Web, from the CNR-Pisa Visual Computing Group, includes code for 3D Delaunay triangulations

Constrained Delaunay triangulations

See also mesh generation and manipulation.

Super Delaunay, a commercial fully dynamic constrained Delaunay triangulation package from David Kornmann (description only). Interactive demo versions for Sun Solaris and Linux are available here (binaries and data only). Demo versions for other architectures are available from the author.
Dani Lischinski's incremental constrained Delaunay triangulation program CDT.
Robert J. Renka's TRIPACK, Collected Algorithms of the ACM #751, computes constrained Delaunay triangulations, convex hulls, polygon areas, nearest neighbors, and shortest paths. (FORTRAN)

Medial axes and Voronoi diagrams of line segments

Voronoi Diagrams of 2D Shapes by Martin Held. Robust computation of Voronoi diagrams and offset curves for planar shapes bounded by straight line segments and circular arcs. The web site only describes the software and illustrates some of the results; the code is available by email.
Voronoi diagrams of line segments by Toshiyuki Imai (FORTRAN)
Robert L. Ogniewicz's image skeletonization software
avd, a LEDA extension package to compute abstract Voronoi diagrams in the plane, by Michael Seel. Code for Euclidean Voronoi diagrams of points and line segments is included.

Miscellaneous

VoronoiImage by Marc Grundland: an image processing program that uses nested Voronoi diagrams to acheive stained-glass effects (Mac binaries only) [Warning: frames!]
Alpha Shapes project at NCSA [Warning: frames!]
- Online demo (also requires Java and VRML)
- User's guide
- Downloading instructions
- Installation instructions
- Documentation from Ernst Mücke's GeomDir

Operations on polygons

Relevant pages from DCGS:

Point location

Paul Bourke describes how to tell if a point is inside a polygon and how to calculate the area of a polygon, with C source code. From his Geometry pages.
PNPOLY: William Randolf Franklin's point-in-polygon test, from the comp.graphics.algorithms FAQ
Eric Haines' point-in-polygon code and experimental results from Ray Tracing News, Volume 5, Number 3. Newer, more optimized code is also available in Graphics Gems IV.

Boolean operations

Constructive Planar Geometry by David Eberly: standard boolean operations on generalized polygons (only intersection is actually implemented)
Boolean operations on polygons by Matej Gombosi.
Boolean operations on sets of 2d polygons, by Klaas Holwerda, includes interactive visualization software (Sun and Windows only) and a complete description of the algorithms and data structures used. Results are "snap-rounded" to the integer grid.
Polypack, a package of routines to manipulate polygons, by David J. Kennison (FORTRAN, description only)
Alan Murta's generic polygon clipping library computes intersections, unions, and differences between possibly self-intersecting, possibly multiply-connected polygons, possibly with holes.
Klammer Schutte's clippoly computes intersections and differences of nonconvex polygons. (Warning: The source contains over 10,000 lines of C++ code!)
- An updated version of clippoly by Gregg Keichtman runs on a few more platforms than the original version. A Macintosh PowerPC executable and MATLAB versions are also available.
- A much smaller version of the same algorithm, written in C by Alexy Nitikin and Michael Leonov, also handles polygons with holes. [New URL]

Triangulation and quadrangulation

See also the sections on Voronoi diagrams and Delaunay triangulations and mesh generation and manipulation.

FIST: Fast Industrial-Strength Triangulation, by Martin Held, computes triangulations of polygons with holes, even in the presence of degeneracies or self-intersections. The web site only describes the software and illustrates some results; the code itself is avialable by email.
Fast polygon triangulation code (also available here) by Atul Narkhede and Dinesh Manocha, published in Graphics Gems V, triangulates polygons in O(n log^* n) expected time using a randomized incremental algorithm of Raimund Seidel. Their code also handles polygons with holes.
Polygon triangulation code by Ken Sloan, which optionally tries to merge as many triangles into quadrilaterals as possible.

Miscellaneous

Thomas Auer and Martin Held's RPG implements several heuristics for randomly generating simple polygons from a given set of vertices. See also Auer's master's thesis.
Source code from "Computing Common Tangents Without a Separating Line" by David Kirkpatrick and Jack Snoeyink (WADS 1995)

Mesh generation and manipulation

See also the sections on Delaunay triangulations and geometric modeling.

Relevant pages from DCGS:
- Mesh generation
- Mesh manipulation
Other collections:
- Meshing programs, libraries and related programs collected by Christian Klesper for his extensive survey of meshing programs. [Warning: some parts of the survey require a frames-capable browser.]
- Mesh generation software from Robert Schneiders' Mesh Generation & Grid Generation on the Web.
Barry Joe's GEOMPACK (FORTRAN)
Scott Mitchell's triangulation results includes code to generate linear-size nonobtuse triangulations of polygons, using the circle-packing algorithm of Bern, Mitchell, and Ruppert. (MATLAB and C++)
EasyMesh by Bojan Niceno builds constrained and conforming Delaunay triangulations (and their dual Voronoi diagrams) and performs local mesh coarsening, refining, relaxation, and smoothing. Written by an applied physicist using algorithms developed by other applied physicists.
Triangle, a comprehensive package by Jonathan Shewchuk for generating Delaunay triangulations and guaranteed-quality meshes.
- Research credits, including Shewchuk's own paper about the program
- Code for the adaptive precision floating point predicates used in Triangle are available separately.
QMG: mesh generation and related software by Steven Vavasis
- Source code (C++ and MATLAB)
The Chopper, a semi-automatic hexahedral mesh generator, by the Finite Element Modelling Group, Queen's University of Belfast (descriptions only)
STRIPE breaks a polygonal model into few triangle strips.

Geometric modeling

See also the section on mesh generation and manipulation.

Relevant pages from DCGS:

Binary space partition trees

A BSP tree library in ANSI C, by A. T. Campbell, III; a slightly older version in C++ is also available.
Bretton Wade's binary space partition tree source and demos for the Mac and Win95 machines. (An X version is reportedly in the works.) Several more BSP implementations are listed in his excellent BSP FAQ.
Large geometric data sets, primarily models of Soda Hall, courtesy of Seth Teller.

Collision detection

SOLID version 2.0: collision detection for moving three-dimensional objects, by Gino van den Bergen.
Stephen Cameron's implementation of an algorithm of Gilbert, Johnson, and Keerthi to compute distances between convex polyhedra. Qhull is required for some features.
Geometric software by Brian Mirtich:
- V-Clip collision detection library
- The Lin-Canny closest features algorithm
A fast triangle-triangle intersection test by Tomas Möller, from journal of graphics tools, 2.2:25-30 (1997)
Algebraic and geometric software from the UNC Research Group on Modeling, Physically-Based Simulation and Applications
- I_COLLIDE: collision detection for convex polyhedra
- RAPID: collision detection for arbitrary polygonal models

Reconstruction

Surface reconstruction software by Hughes Hoppe and others, and accompanying range data for several 3d models
Nuages, a package for 3D reconstruction from cross sectional data, from the PRISME project at INRIA Sophia-Antipolis

Simplification

Michael Garland's terrain simplification programs scape and terra.
Qslim: surface simplification code, using quadric error metrics, by Michael Garland
Jade, a tool for simplifying triangular meshes, from the CNR-Pisa Visual Computing Group.
Simplification Envelopes from the UNC Research Group on Modeling, Physically-Based Simulation and Applications

Visibility computation

Heather Alef's X-windows visibility graph exploration tool
Fast, minimum storage ray-triangle intersection by Tomas Möller and Ben Trumbore, from journal of graphics tools 2.1:21-28 (1997)
VisPak: a package of visibility-related algorithms implemented by Helen Pinto and Lillanne Jackson at the University of Lethbridge. Requires LEDA to compile, but Sun binaries are provided.
Michel Pocchiola and Gert Vegter's Greedy Flip Algorithm in Action, an implementation of the authors' algorithm for constructing visibility complexes by evolving pseudo-triangulations.
Visibility Graphs and Motion Planning by Kittiphan Techakittiroj (Windows 3.1 executable only)

Visualization tools

You should also look for the thing being visualized! See also my list of programs that can be run over the web.

Relevant pages from DCGS:
- Visualization tools
- Interactive visualizations
UNREAL, a GeomView module for "hand-drawing" mathematical objects, by Nina Amenta, Danek Duvall, and Tim Rowley
Javier Elices's GeomView module for visualizing the Dobkin-Kirkpatrick hierarchy
Graphviz, tools for viewing and interacting with graph diagrams, by John Ellson, Eleftherios Koutsofios, and TopoVista: fly over USGS Digital Elevation Models, using right triangular irregular networks to maintain variable levels of detail, courtesy of Will Evans and Gregg Townsend. Requires OpenGL and Glut.
DUST, a program for visualizing Voronoi diagrams, Delaunay triangulations, minimum spanning trees, and matchings in various metrics. From Michael Jünger's research group at Universität zu Köln.
Peek by Gordon Kindlmann, a program for visualizing high-dimensional polytopes through their cross-sections and projections (or as Amenta and Ziegler would have it, their shadows and slices).
Cinderellas Café, a "dynamic geometry" Java program written by Ulrich Kortenkamp and Jürgen Richter-Gebert, dynamically maintains sets of geometric objects (points, lines, circles, and conics) as the user moves their defining points around, provides primal and polar views of the same objects, supports spherical and hyperbolic geometry, and even includes some automatic theorem proving! A demo version is available. Information is currently available in German only.
Geomview, the Geometry Center's 3d geometric visualization program, written by Stuart Levy, Tamara Munzner, Mark Phillips, and a cast of thousands. Also available from a mirror site in Berlin.
JGV, a successor to GeomView written in Java, also from the Geometry Center. (Java, source not available)
Bob Lewis's homogeneous coordinates and duality visualization program VideHoc (SGI executable only)
Michael Murphy's Ranger, a program for visualizing high-dimensional nearest neighbor and orthogonal range searching data structures. From Steve Skiena's Practical Algorithm Reference
The GeoPrO distributed visualization enviornment, by Pedro J. de Rezende, Guilherme Albuquerque Pinto, Alexandre Volpim, and Frederico Guth. (description only so far)
Otfried Schwarzkopf's extendible drawing editor Ipe
Toposcope: Automatic visualization of the topology of 2D cell complexes by Jorge Stolfi, Rober Marcone Rosi, C. F. Xavier de Mendonça, and L. P. Lozada
Shastra, a geometric modeling and visualization system being developed at Purdue University (descriptions only)
Software on the Web, from the CNR-Pisa Visual Computing Group, includes code for volume visualization.
ZEUS, an algorithm animation system developed at DEC SRC (Modula-3)

Other

Algorithms for partitioning multi-dimensional data sets, collected by Charles Alpert
DemoKin, a demonstration of kinetic data structures for convex hulls, closest pairs, Voronoi diagrams, and minimum spanning trees, by Julien Basch, Leo Guibas, Craig Silverstein, and Li Zhang. Requires LEDA, XForms, and OpenGL to compile; an SGI executable is available.
MAXRAD: software to find the maximum radius sphere touching each point (atom) in a set (molecule) using inversion and convex hulls, by Todd Yeates. (FORTRAN)

From: http://compgeom.cs.uiuc.edu/~jeffe/compgeom/code.html#mesh

Web 3D platform

Unity - A good commercial engine. Development only supports MacOS.

http://unity3d.com/

Blink 3D

http://www.pelicancrossing.com/index.htm

Commercial. Provides a free version.

Emma3D

http://emma3d.sourceforge.net/

Open-source.

Saturday, February 21, 2009

Bezier Curves

Linear Bézier curves

Given points P₀ and P₁, a linear Bézier curve is simply a straight line between those two points. The curve is given by

$\mathbf{B}(t)=\mathbf{P}_0 + t(\mathbf{P}_1-\mathbf{P}_0)=(1-t)\mathbf{P}_0 + t\mathbf{P}_1 \mbox{ , } t \in [0,1]$

and is equivalent to linear interpolation.

[edit]Quadratic Bézier curves

A quadratic Bézier curve is the path traced by the function B(t), given points P₀, P₁, and P₂,

$\mathbf{B}(t) = (1 - t)^{2}\mathbf{P}_0 + 2(1 - t)t\mathbf{P}_1 + t^{2}\mathbf{P}_2 \mbox{ , } t \in [0,1].$

A quadratic Bézier curve is also a parabolic segment.

TrueType fonts use Bézier splines composed of quadratic Bézier curves.

[edit]Cubic Bézier curves

Four points P₀, P₁, P₂ and P₃ in the plane or in three-dimensional space define a cubic Bézier curve. The curve starts at P₀ going toward P₁ and arrives at P₃ coming from the direction of P₂. Usually, it will not pass through P₁ or P₂; these points are only there to provide directional information. The distance between P₀ and P₁ determines "how long" the curve moves into direction P₂ before turning towards P₃.

The parametric form of the curve is:

$\mathbf{B}(t)=(1-t)^3\mathbf{P}_0+3(1-t)^2t\mathbf{P}_1+3(1-t)t^2\mathbf{P}_2+t^3\mathbf{P}_3 \mbox{ , } t \in [0,1].$

Modern imaging systems like PostScript, Asymptote and Metafont use Bézier splines composed of cubic Bézier curves for drawing curved shapes.

Constructing Bézier curves

[edit]Linear curves

Animation of a linear Bézier curve, t in [0,1]

The t in the function for a linear Bézier curve can be thought of as describing how farB(t) is from P₀ to P₁. For example when t=0.25, B(t) is one quarter of the way from pointP₀ to P₁. As t varies from 0 to 1, B(t) describes a curved line from P₀ to P₁.

[edit]Quadratic curves

For quadratic Bézier curves one can construct intermediate points Q₀ and Q₁ such that as t varies from 0 to 1:

Point Q₀ varies from P₀ to P₁ and describes a linear Bézier curve.
Point Q₁ varies from P₁ to P₂ and describes a linear Bézier curve.
Point B(t) varies from Q₀ to Q₁ and describes a quadratic Bézier curve.

Construction of a quadratic Bézier curve
Animation of a quadratic Bézier curve, t in [0,1]

[edit]Higher-order curves

For higher-order curves one needs correspondingly more intermediate points. For cubic curves one can construct intermediate points Q₀, Q₁ & Q₂ that describe linear Bézier curves, and points R₀ & R₁ that describe quadratic Bézier curves:

Construction of a cubic Bézier curve
Animation of a cubic Bézier curve, t in [0,1]

For fourth-order curves one can construct intermediate points Q₀, Q₁, Q₂ & Q₃ that describe linear Bézier curves, points R₀, R₁ &R₂ that describe quadratic Bézier curves, and points S₀ & S₁ that describe cubic Bézier curves: