Difference between revisions of "User:NyahCh3ck20/Proposal"

(Gsoc 2013 Proposal)
Line 100: Line 100:
===  Links ========
===  Links ===
[1] CodePatch(Sample linked list that holds the matrices and inverses and corresponding directories together with the sample       implementation of the Inverse of a transformation function).
[1] CodePatch(Sample linked list that holds the matrices and inverses and corresponding directories together with the sample       implementation of the Inverse of a transformation function).
[2] Geometric Transformations and Inverses:
[2] Geometric Transformations and Inverses:

Revision as of 14:04, 25 April 2013

Personal Information

NAME : Check Nyah Watad Wallah EMAIL: check.nyah@gmail.com IRC: Ch3ck

Background Information

I am a freshman Computer Engineering Student at the University of Buea, South West Region,Cameroon. After wining the 1st prize for Programming among the freshman year students at my university. I have founded a programmers club to help develop the coding skills among members of my university community

Project Information


              PUSH ON GEOMETRY.

Brief Project summary

The pull routine takes a specific node on a CSG tree, walking down to the primitive shapes restoring the geometric transformations(scaling, translation or rotations) at each stage down the CSG tree traversal based on reversing all the geometric transformations that occured on the primitive shapes located at the leaf. Pull routine also stores the local coordinate systems ate each point during the traversal from the primitives up to the given initial node. All transformation matrices visited along the tree will be set to their original tranformation matrices. This command will fail if no changes occured to the primitive shapes at the leaves of the csg tree.

Detailed Project Description

Introduction =

The Pull/unpush command/routine is a high priority project for BRL-CAD. The pull command seeks to restore the original state of the csg tree from any particular node after the push command has been executed. However, the Push command is used to walk the geometry tree from a specified top to the primitive level, collecting the matrix transformations such as (translations, rotations or scales) applied to new assemblies using matrix edits(oed command). The push then applies the matrix tranformation parameters to the primitives, eliminationg the need for storing the various matrix transformations thereby setting them to identity matrices. This process however looses any local coorrdinate system used in constructing the geometric objects. The pull routine seeks to restore the original tree state by reversing any tranformation operations performed on the primitive shapes from a designated top node on the csg tree. Here, I would like to show my detailed proposal in solving this summer's project. My code patch will have a sample routine that takes as argument a designated node(such as a primitive) and performs the Inverse of any rotation, Inverse of any translation and the inverse of a scale.) and performs the matrix inverse the primitive matrix.

The Working of the Pull Routine

Syntax pull <objects>

arguments <objects> valid brlcad objects currently in database.

The Pull routine takes as arguments a valid object, moves down the tree and performs an inverse rotation which is stored in a list, inverse scale and inverse translation which is stored on the list and transforms the primitive object by the Inverse transformations and recursively inserts the original matrix transformations on the tree as it moves up from the primitive

Matrix Transformations BRL-CAD uses three main transformations on objects stored in a 4x4 matrix defined by 'mat_t' data type Assuming the 4x4 matrix is represented as shown below [0 ][ 1][ 2][ 3] [4 ][ 5][ 6][ 7] [ 8][9 ][10][11] [12][13][14][15]

The rotation operation is represented by the 3x3 matrix [0 ][ 1][2 ] [3 ][ 4][ 5] [6 ][ 7][ 8]

The scale transformation is represented by the diagonal matrix [0][4][ 8] or [0] 0 0 0 0 [4] 0 0 0 0 [8] 0 0 0 0 1

The translation transformation is represented by 1 0 0 [3] 0 1 0 [7] 0 0 1 [11] 0 0 0 1

The Inverse of the various transformations will be computed by the routine

/**************************************************************** void InverseTransform(mat_t transf); shown in the code patch

     **********        or  ***************
   a preprocessor directive
#define InverseTransform(transf)   //so as to increase speed of execution.

The Mathematics of the Inverse Transformation

Inverse Rotation: In Euclidean geometry, a rotation is an example of an isometry, a transformation that moves points without changing the distances between them. Rotations are distinguished from other isometries by two additional properties: they leave (at least) one point fixed, and they leave "handedness" unchanged. Since BLR-CAD represents a rotation by the 3x3 matrix, an Inverse of a rotation would be the transpose of the 3x3 matrix so if RotA(3x3 rotation), Inverse(RotA) = Transpose(RotA).

Inverse Scale: Scaling transformations stretch or shrink a given coordinate system and as a result change lengths and angles. So, scaling is not an Euclidean transformation. The meaning of scaling is making the new scale of a coordinate direction p times larger. In other words, the x coordinate is "enlarged" p times. This requirement satisfies x' = p x and therefore x = x'/p. Scaling can be applied to all axes, each with a different scaling factor. For example, if the x-, y- and z-axis are scaled with scaling factors p, q and r, respectively, the inverse transformation matrix is: Inv(SclA) = 1/p 0 0 0 1/q 0 0 0 1/r

Inverse Translation: A translation is an affine transformation with no fixed points. Matrix multiplications always have the origin as a fixed point. Nevertheless, there is a common workaround using homogeneous coordinates to represent a translation of a vector space with matrix multiplication: Write the 3-dimensional vector w = (wx, wy, wz) using 4 homogeneous coordinates as w = (wx, wy, wz, 1). so the Inverse of a translation is simply the reverse of the matrix. if TrnA = (a, b ,c , d) Inverse(TrnA) = (-a, -b, -c, -d)

Overall Structure Pull routine

The pull routine will use the inverse transformations to restore the primitive back to its original state, taking note of the local geometric transformations after each inverse transformation which will be stored together with the original matrix transformations as it moves back up the tree.

However,brlcad already has the functionality for performing matrix operations on objects as in(src/libged/push.c, xpush.c). I can use the InverseTransf() as a subroutine in the pull operation and simply use the MAT_COPY directive to copy the various 4x4 original matrix transformations to the corresponding node up the tree from the leaf. So, here is a summary of the pull command

*. create a structure to hold the original matrix and corresponding local coordinate systems while calling InverseTranf().

*. create a loop to move down the tree to the leaf nodes while recording the transformations *. pull leaf() routine : which runs in parallel restore the original state of the primitive objects.(leafs) *. mat_restore() routine: which restores the original matrix transformation and coordinate system at each node. Tests and Verification:

I believe test driven development would be key in finding and fixing problems with the pull routine and then with more tests to ensure the code functions correctly and its bulletproof to all forms of object inputs. This will be enhanced with the creation of a special regression test for the pull command to avoid modification of unwanted nodes/objects.Also, this command will be included among the MGED commands and a well written manual will be made so support the usage of the command.


[1] CodePatch(Sample linked list that holds the matrices and inverses and corresponding directories together with the sample implementation of the Inverse of a transformation function). Link:

[2] Geometric Transformations and Inverses: