User:Izak
Contents
Project Proposal
PERSONAL INFORMATION
Name: Isaac Kamga.
E-mail: u2isaac@gmail.com.
Internet Relay Chat Username: Izak.
Phone: +237 74 10 62 97.
Brief Background information.
I am a final year Master of Science in Computer Science student at the University of Buea , Cameroon , Africa holding a Bachelor of Science degree in Mathematics.I have worked on various data structuring, algorithmic and compiler-related individual and team projects in the University community which I really enjoyed. By June , I would have rounded up with my thesis and will be available for 40+ hours weekly to implement a heart surface primitive for BRLCAD software.
PROJECT INFORMATION
PROJECT TITLE: Implementation of a heart primitive.
PROJECT SUMMARY
We live in a three dimensional world and we frequently have to consider objects which have surfaces - whether these are terrains on planets ,the surface of a gadget, or organs in our internal worlds.In recent times, the need to visualize the surfaces of internal organs such as the heart , liver , brain ,just to name a few, has escalated due to the explosion in cases of heart disease and cancer. There is an imminent need for the BRLCAD software, which aspires to be the best computer assisted design software, to possess a heart primitive which can assist users like medical personnel model the heart and plan the effective treatment of cardiac disease.The implementation of a heart primitive also stands as a great opportunity to provide open source C code for the hacker community which can aid in the implementation of other similar geometries which are based on the sextic equations. I intend to implement a heart primitive for the BRLCAD software simply by writing a set of routines( callback functions).These routines will be stored in three (3) files namely hrt.c , hrt_brep.cpp and hrt_mirror.c as is the naming convention of the BRLCAD software primitives. The hrt.c file will contain routines ( functions ) that execute ray intersection with a heart,a geometric analysis of the heart ,a geometric representation of the heart and constructive solid geometry (C.S.G.) modelling . The hrt_brep.cpp is a piece of source code written in the C++language which executes a boundary representation of a heart. Finally , hrt_mirror.c will provide mirror support for the heart primitive against a particular plane .
PROJECT DESCRIPTION
In this section of this proposal, I give a detailed description of how I am going to implement the heart primitive. In order to implement a heart primitive for the BRL-CAD software, we have to write a set of routines.These routines will be stored in the hrt.c file that help for ray intersection, geometric representation and analysis of the a heart as well as the combination of regions using boolean operations which assist BRLCAD users in constructive solid geometry (C.S.G.) modeling.
--hrt.c Here, we implement ray intersection , geometric analysis , geometric representation and combine several elliptical paraboloids to form a heart. This hrt.c file is the heart of the heart primitive. We include common.h for portability , system headers like stdio.h, math.h and stddef.h, db.h for database interactions, raytrace.h and rtgeeom.h .
The sextic equation given below by the formula
F(x,y,z)=0 ------- (1)
where F(x,y,z) = (x^2 + 9/4*y^2 + z^2 - 1 )^3 - x^2*y^3 - 9/80 * y^3 * z^3
defines the surface of the heart and it happens to be symmetric along the x-axis. We need to Solve this equation for x^2 inorder to enable us plot the heart curve in three dimensions. To do this, we rewrite the equation into a function of two variables P(y,z) which yields Q(x,y). We get x = Q(y,z) = sqrt(P(y,z)). The sextic equation above gets sinplified to the formula
(a + 9/4*y^2 + z^2 - 1)^3 - a*y^3 - 9/80*y^3*z^3 = 0 -------------------- (2)
by a = P(y,z) = x^2.
This gets reduced to a cubic (of power 3) polynomial given below
a^3 + b*a^2 + c*a + d = 0-------------(3)
where
b = P1(y,z) = 27/4 * y^2 + 3 * z^2 - 3.
c = P2(y,z) = 405/16 * y^4 - 27/4 * y^2 + z^4 + 9/2 * z^2 * ( y^2 + 1) + 1.
d = P3(y,z) = 729/64 * y^6 + 243/16 * z^2 * y^4 + 27/4 * y^2 * z^4 - 27/4 * y^2 * z^2 - 81/4 * y^4 + 9/2 * y^2 + z^6 - z^4 + z^2 - 1.
The cubic equation in (3) can be solved algebraically using a division method or a decomposition as referenced in the research articles below (See "Links to code and algorithms you intend to use" section in this proposal). The roots of the equation will be Q(x,y) = {a1,a2,a3,a4,a5,a6} where ai = Q(x,y) for i in {1,2,3,4,5,6}. We are now able to plot the heart curve in 3D.
Ray tracing
Now we go over to how I intend to evaluate a ray against the sextic equation in (1).
First of all , I will parametrize the sextic surface equation in (1) by converting it into the form
x = F1(u,v) ----------- (4)
y = F2(u,v) ----------- (5)
z = F3(u,v) ----------- (6)
I intend to compute the normal vector (ray) using the cross product of the partial derivatives of the coordinate functions. That is,
F1u(u,v) = partial(F1(u, v)) / partial(u) ------------- (i) F1v(u, v) = partial(F1(u, v)) / partial(v) -------------(ii) F2u(u, v) = partial(F2(u, v)) / partial(u) -------------(iii) F2v(u, v) = partial(F2(u, v)) / partial(v) -------------(iv) F3u(u, v) = partial(F3(u, v)) / partial(u) --------------(v) F3v(u, v) = partial(F3(u, v)) / partial(v) --------------(vi)
where the vectors
tu(u, v) = <F1u(u,v), F2u(u,v) , F3u(u,v)> and tv(u, v) = <F1v(u,v) , F2v(u,v) F3v(u,v)> are tangents to the surface. Thus, we obtain the vector perpendicular to the tangent ( the normal to the surface) which is N(u, v) = p(u, v) / || p(u, v) || where p(u, v) = tu(u,v) X tv(u,v). The normal to the surface N(u,v) is the ray touching the heart from a particular point in 3D.
Rendering
Here, I discuss how I intend to do visualization (geometric representation and analysis). I intend to do this by finding the intersection points between the line (light ray ) and the heart. We simply will write a line-heart test which tells us if a point on the heart surface intersects with the heart. The points of intersection are those that satisfy the line equation and the equation for the surface of the heart at the same coordinates x, y, z. Here , we equate (1) and the equation of the line given below by
X = o + dL --------------- (7)
where d > 0 , X = (x,y,z) is in R^3 and L is the direction of the line.
To search for points that are on the line and on the heart means combining the equations and solving for d. When equations are combined , expanded and rearranged , we get a quadratic equation
a*d^2 + b*d + c = 0 ---------------(8)
which can be solved using the quadratic formular.
d = -b + sqrt(b^2 - 4 * a * c) / 2*a and d = -b - sqrt(b^2 - 4*a*c) / 2*a.
If the value of b^2 - 4*a*c is less than zero, then it is clear that no solutions exist, that is, the line does not intersect the heart.If it is zero, then exactly one solution exists, that is, the line just touches the heart in one point.If it is greater than zero, two solutions exist, and thus the line touches the heart in two points (the entry and exit point).
Boolean operations
Intersection In order to write the intersection of different primitives with the heart primitive , I will solve for the 3D surface R(x,y,z) using the method given above (Equating (1) and the equation of the given primitive).
1. We create bounding box for the heart. 2.We transform the points on the heart to points on a heart centered at the origin, with a height along the the positive Z axis and a vertex V. 3.We find the point of intersection W of a line with the surface of a heart and the vector normal to the tangent plane at the point of intersection. 4.We write routines to interact with the values of the heart in the database.For example, routine to free the database storage of he heart, change database formats and export the heart from the database. 5. We then write routines to compute the volume, surface area and centroid of the heart.
Routines to print the heart , get curve points, plot the heart and tesselate will be written.
6. We write routines to return the normal, entry and exit points of a ray .
LINKS TO CODE OR ALGORITHMS WHICH YOU INTEND TO USE
Research papers
1.Taubin, G. "An Accurate Algorithm for Rasterizing Algebraic Curves." In Second ACM/IEEE Symposium on Solid Modeling and Applications Proceedings. 221-230, May 1993.
2.Nordstrand, T. "Heart." http://jalape.no/math/hearttxt.
3."A Generalization of Algebraic Surface drawing" by James F. Blinn.
4.Wolfram mathworld's sextic equation:http://mathworld.wolfram.com/HeartSurface.html
5.Solving sextic equations by division , Raghavendra G. Kulkarni.
6.Solving sextic equations by decomposition , Raghavendra G. Kulkarni.
Pictures
1.Three dimensional heart with sextic equation:
2.Two dimensional heart with sextic equation:
3.Three dimensional heart centered at origin according to Taubin,G:
Code patch
http://sourceforge.net/p/brlcad/patches/174/
DELIVERABLES
Pre mid term evaluation period
- Ray intersection with heart.
- Geometric analysis and representation
- Compute heart metrics like surface area and volume of heart.
- Testing of hrt.c.
Post mid term evaluation period
- Combinations and regions using booolean operations.
- Database interactions.
- Intersections with other primitives.
- Integrating and documenting heart primitive into BRLCAD
DEVELOPMENT SCHEDULE AND TIMELINE
May 27th : Community bonding period
(3 weeks)
- Study BRLCAD manuals,tutorials series and documentation concerning hacking.
- Compile BRL-CAD source code ,Study code base and remove bugs.
- Discuss with other developers and BRLCAD mentors to refine mailing-list etiquette.
- Study the src/librt/primitives/*/* and /include libraries.
- Acquaint myself with necessary software like svn
June 17th to July 26th : Work period (Pre-mid term evaluation)
(1 week)
- Ray intersection with heart.
- Testing and debugging routines.
(2 weeks)
- Geometric analysis and representation.
- Testing and debugging routines.
(1 week)
- Compute heart metrics like surface area and volume of heart.
- Testing and debugging routines.
(2 weeks)
- Testing routines in hrt.c code.
- Submission of hrt.c to mentors for corrections.
June 29th to August 2nd : Mid-term evaluation
(1 week)
- Submission of preliminary hrt.c to Google.
Aug 5th to Sept 13th : Work period (Post mid-term evaluation)
(2 weeks)
- Combinations and regions using
- -intersection operation.
- -union operation .
- -exclusion operation.
(2 weeks)
- Database interactions.
- Intersections with other primitives.
(2 weeks)
- Testing and debugging of hrt.c.
Sep 16th to Sep 27th: Testing and Documentation period
(1 week)
- Integrating heart primitive into BRLCAD.
- Final testing and debugging of src/librt/primitives/hrt/hrt.c code.
- Documenting heart primitive in BRL-CAD.
- Submit hrt.c code to Google.
(1 week)
- Final submission of hrt.c code to Google.
TIME AVAILABILITY.
I am at the last phase of my M.Sc. research and will be done with the thesis before June. I will have ample time to code fulltime for 40+ hours weekly till the end of the summer holidays.My thesis defense will take place after the summer holidays . Also, while awaiting defense and graduation in December 2013 after the summer , I will be available for some months to do any polishing and maintainance work given to me by BRLCAD mentors.
WHY BRL-CAD?
First of all, I really believe that software can change the world by providing new technologies and that software should be free. I choose BRLCAD because it is a not-for-profit technology organization which offers me the opportunity to assist the United States Army Research Laboratory with tools which help them simulate and visualize their combat vehicle systems and war events. Working with BRLCAD also helps me contribute over the long-term and gain status within the hacker community based on my mathematical/Computing background and academic interests. Although I have not contributed before to opensource ,I see implementing a heart surface primitive as a long-awaited opportunity to provide more primitive options (adding a heart to the raytrace library which is the heart of BRLCAD) for the BRLCAD software and a jumpstart to my continued contribution to open source software through BRLCAD.This project will also help BRLCAD users to build three-dimensional models related to the heart and love - a virtue we really need in our world today.
WHY YOU?
I am a final year M.Sc. student in Computer Science at the University of Buea (www.ubuea.net) , Cameroon , Africa and a holder of a B.Sc. in Mathematics & Computer Science. I am currently rounding up with my research thesis on business process compliance. I have a good background and intuition in Mathematics and algorithms as well as C/C++ programming. In the past , I worked on various data structuring and algorithmic individual and team projects in the University community which I really enjoyed. For example , I built mini-compilers flex/bison to reason about and infer the regulatory compliance in associated business process graphs . Also , I worked within a team to implement red black trees and variants like order statistics trees , interval trees and persistence trees (over 6000 lines of C code). I was enthused collaborating in teams with other bright thinkers . I was the best on some projects and mediocre on some others - but I really learnt the importance of communicating and working in teams with other smart individuals. I was born into an extended family of researchers in Research institutions and Universities under the Cameroonian government.This gave me the passion to become a researcher for not-for-profit organizations and contribute to the open source community. With this upbringing ,background and experience, I think I have the necessary skills to implement a heart surface primitive for the BRLCAD software. I am familiar with various open source software engineering tools like svn, gcc, gdb ,emacs ,etc and switched to Linux distributions ( using Red Hat and Ubuntu ) since 2010. Also, I am at the last phase of my research and will be done with the thesis before June. I will have ample time to code away the summer holidays . Lastly , I will make sure I communicate my progress , problems encountered and further work to my mentors in Weekly reports to fascilitate the supervision and management of the project. I will also discuss with mentors for other needed clarifications on IRC chat.
ANYTHING ELSE?
I think it would be great for BRLCAD to select me for various reasons. Firstly , it will greatly encourage the programmers around my community and country to come up to hackerdom standard and contribute to open source projects. It will also attract and encourage a lot of young ones in my country and continent towards the computing field as a whole. Also, BRL-CAD will gain the reputation of encouraging equal opportunity and ethnic diversity by helping to groom more hackers from underrepresented minority backgrounds in computing like Africa.
