Wednesday, May 30, 2012

Flashback: RSimp

Simplification Through Refinement
Back in 1999, Dmitry Brodsky created a simplification algorithm that works by refining a very crude initial approximation. The algorithm is extremely fast, and linear for fixed output size. At the same time, it has good output quality, once the output model is larger than a few hundred polygons. The algorithm works particularly well when input models are large, since the number of linear passes over the input is proportional to output size.

Hindsight
Steady interest in RSimp has continued over the years, because of its unusual approach to simplification. It could be improved to respond to model attributes, particularly normal maps, which are now standard in the gaming industry. It could also be specialized further for very large models.

Software
RSimp 3.8 source is available. Reads ply and smf models. Shouldn't be any platform dependencies. Written in C++ by Dmitry Brodsky. Does not adapt to mesh boundaries or attributes. RSimp 3.9 is also available. Reads ply and smf, no platform dependencies. Updated in C++ by Prasun Choudhury and Andrew Raij. Improvements over 3.8: responds to mesh boundaries, and implements error based control of output quality/size.

Publications
  • P. Choudhury, B.A. Watson. (2002). Completely adaptive simplification of massive meshes. Northwestern U., Dept. Computer Science, Technical report NWU-CS-02-09. (gcites) (pdf)
  • D. Brodsky, B.A. Watson (2000). Model simplification through refinement. Proc. Graphics Interface (Montreal, May), 221-228. (gcites) (pdf)
  • D. Brodsky & B.A. Watson (2000). Model simplification for interactive applications. Poster and extended abstract, Proc. IEEE Virtual Reality 2000 conference, 286. (gif)
  • D. Brodsky & B.A. Watson (2000). Parallelization, small memories and model simplification. Proc. 11th Western Canadian Computer Graphics Symposium, (Panorama, Canada, March), 75-84.
  • D. Brodsky, B.A. Watson (1999). R-Simp: model simplification in reverse, a vector quantization approach. Proceedings 10th Western Canadian Computer Graphics Symposium, (Banff, Canada, March), 83-92.
  • D. Brodsky, B.A. Watson (1999). R-Simp: model simplification in reverse. Graphics Interface 99 conference poster abstracts, 39-40 (London, Canada, June).

Imagery

Reverse simplification
Because RSimp refines rather than simplifies, it produces drastic simplifications quite quickly, while other algorithms actually take longer to produce less output. Here, time vs. output size for RSimp, QSlim, and vertex clustering.

Simplification of Stanford's dragon  
Quality is worse than the slower qslim's, but much better than with faster vertex clustering.