guansy@cs.tamu.edu (Sheng-Yih Guan) (10/02/90)
You all have seen a nice posting from Paul Heckbert on methods of performing resampling when an image is being warped by a non-invertible deformation. The following is my summary and Jeffrey's suggestion for inverting mappings: Supplementing to Heckbert's reference list, there is one other article - "Real-time manipulation of texture-mapped surfaces" by Oka et a. (SIGGRAPH'87, 181-188) - which I have found to be very interesting. In that article, the mapping function is approximated by a linear function on a 8 x 8 block basis. Therefore, the inverse of the mapping function can be easily computed and be applied to a small region of the destination space one at a time. The result in my implementation turns out to be satisfactory. About how to assign an intensity value to a given pixel in the destination space, one thing need to be considered. Depending on the ratio of the size of the corresponding texture area (source) to the output pixel, we do either interpolation, averaging, or decimation. Different types of filters for doing this are discussed in Heckbert's article on texture mapping (pointed out by Jeffrey, too). >A generally useful way of inverting mappings is known as >error correction: basically, you start out with a guess, say x0,y0, >then evaluate x0' = r(x0,y0) and y0' and compute the error between >these values and the desired values x' y'. You then determine the >correction to be applied to x0,y0 by evaluating the partial >derivatives dx'/dx, dx'/dy, dy'/dy and dy'/dx in the neighborhood >of x0,y0. You then pick a correction direction dy/dx so that >the transformed direction dy'/dx' is in the opposite direction to >the error. The amount of correction is set by a gain factor or >"learning rate". For a linear mapping, a gain of 1 will zero the error >on the first iteration. Often a gain of less than 1 will be indicated >by stability considerations. In case it's not clear, the correction >is added to x0,y0, this then becomes the new guess, and this process >is repeated until the error is zero. Not particularly fast, but >it should work if the functions aren't too pathological. > >-Jeffrey Mulligan <jbm@eos.arc.nasa.gov> Million thanks to all of you who has responded to my original posting. -Stanley _ _ _ ___________ | \ /_| / / Visualization Lab /____ ____/ \ \ // / / Computer Science Dept / / _ _ _ _ | | // / / Texas A&M University / / / | | \ / | | | || | |// / / College Station, TX 77843-3112/ / / /| | \//|| | | || / / / /____ Tel: (409)845-0531 / / / -|| | |\/ || | !_!| !__/ /______/ stanley@visual1.tamu.edu /_/ /_/ || !_! || !____!