BSP Tree ??

This is a discussion on BSP Tree ?? within the C++ Programming forums, part of the General Programming Boards category; Hey, I've got a ( very ) messy bit of code that was originally written in watcom c++ and compiled ...

  1. #1
    Registered User
    Join Date
    Sep 2006
    Location
    UK
    Posts
    13

    Cool BSP Tree ??

    Hey,

    I've got a (very) messy bit of code that was originally written in watcom c++ and compiled as a 32bit dos protected mode exe using dos4gw extender.

    It basically takes a list of lines from a file and creates a Hidden Line drawing.

    In the original Dos app it took a few seconds to complete the image, after getting it to run in a VC6 MFC application it takes about a minute +.

    I only started teaching myself C++ about 8 months ago and this code is way beyond me!

    I fairly sure its a BSP tree, but i can't understand why it's so slow.
    I've searched the net for months and there is lots of info about BSP and i get the concept but it hasn't really helped me understand the code i have.

    If anyone can help me understand why it's so slow, or even better how to make it quicker (or even a different way of getting the same image) it might just stop me from tearing my hair out

    standalone VC 6 project :
    http://www.rayevansengineering.com/S...HiddenLine.zip

    Cheers

  2. #2
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,494
    Well have you tried timing how long the calculation takes vs how long it takes to draw it.
    The first step is to work out where the performance bottleneck is.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  3. #3
    Registered User
    Join Date
    Sep 2006
    Location
    UK
    Posts
    13
    hey,

    The code goes through several loops, reading from the file, rewinding, reading again - to me most of this seems totally unnecessary but it sets up several variables in the process, including the vertice array, and i didn't want to mess with it until i understood it better.

    Adding some TRACE lines after each loop and at other points showed that most of the code took less than a second to complete (which suprised me)

    The bottleneck is on the very last loop where (i think) all of the BSP calculations are done, but like i say this part is totally beyond me !!

    Code:
       for (Pnr=minvertnr;Pnr<=maxvertnr;Pnr++) {
            ptr=V[Pnr].connect;
            if (ptr==&dummy || ptr==NULL) continue;
            Ps=V[Pnr].VT;
    
    	///////////////////////////////////////////////////////////
            for (iconnect=1;iconnect<=*ptr;iconnect++) {
                Qnr=ptr[iconnect];Qs=V[Qnr].VT;
    
                if (Ps.X<Qs.X || (Ps.X==Qs.X && Ps.Y < Qs.Y))
                    {Left=Ps;Right=Qs;}
                else
                    {Left=Qs;Right=Ps;}
    
                ileft=colnr(Left.X);iright=colnr(Right.X);
                if (ileft != iright) {deltay=Right.Y-Left.Y;deltax=Right.X-Left.X;}
    
                jbot=jtop=rownr(Left.Y);
    
                for (I=ileft;I<=iright;I++) {
                    jI= (I == iright ? rownr(Right.Y) : rownr(Left.Y+(Xcoord(I+1)-Left.X) * deltay/deltax));
                    LOWER[I]=min2(jbot,jI);jbot=jI;
                    UPPER[I]=max2(jtop,jI);jtop=jI;
    			}
    
                ntrset=0;
    
    			///////////////////////////////////////////////////////////
                for (I=ileft;I<=iright;I++) {
                    for (J=LOWER[I];J<=UPPER[I];J++) {
                        pnode=SCREEN[I][J];
    
                        while (pnode!=NULL) {
                            trnr=pnode->jtr;
                            trset[ntrset]=trnr;
                            jtr=0;
    
                            while (trset[jtr] !=trnr) jtr++;
    
                            if (jtr==ntrset) {
                                ntrset++;
                                if (ntrset==maxntrset) {
                                    int *p=trset;
                                    trset=new int[maxntrset+=10];
                                    if (!trset) errmess("can't add more triangles to sets"); //maxntrset
    
                                    for (int i=0;i<ntrset;i++) trset[i]=p[i];
                                    delete [] p;p=NULL;
    							}
    						}
                            pnode=pnode->next;
    					}
    				}
    			}
    			///////////////////////////////////////////////////////////
    
    
                linesegment(hpoint(Ps,V[Pnr].z,Pnr),hpoint(Qs,V[Qnr].z,Qnr),ntrset);
                dealwithlinkedstack();
    		}
    Instead of drawing directly to the DC i did create an array of lines first and then dump this array to the DC. Refreshing the view was (almost) instant.

    I have an array of polygons inside a Model Class that i loop through, rotate each point (x,y,z) and draw a line to the DC to create a simple (see through) design view, which is extremely fast.
    I then had to dump these points to a file to test this HiddenLine function. (so reading from a file is not really necessary but i'm not good enough to make it use my polygons directly)
    Last edited by spacecadet23; 09-03-2006 at 02:36 PM.

  4. #4
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,494
    > The code goes through several loops, reading from the file, rewinding, reading again
    Well there's the problem then.
    Using a file to basically simulate an array is just horrible.

    > was originally written in watcom c++ and compiled as a 32bit dos protected mode exe
    Probably some attempt to get past the restricted memory?

    You could just try writing your own from scratch rather than trying to use some old fossil code which has obviously had too many hacks to make it work on the old system, and from what I've read of the code you posted, completely devoid of any useful comments.

    At least then you'll be in a much better position to understand what's going on.

    Maybe this?
    http://faq.cprogramming.com/cgi-bin/...&id=1073086407
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  5. #5
    Registered User
    Join Date
    Sep 2006
    Location
    UK
    Posts
    13
    Thanks for the link, i'll need to read through it properly in the morning.

    > The code goes through several loops, reading from the file, rewinding, reading again
    Well there's the problem then.
    That's what i though at first but after doing some investigation that part of the code is suprisingly quick.
    The loop of code that i posted is the part that takes forever.
    The linesegment() function that is referenced also has several loops, but it was too long to post here.

    Your absolutley spot on.. the old developers told me that they'd hacked it to pieces.

    The entire application (which i am about 90% of the way through a VC conversion) was just a mess, most of the functions and vars were global without the use of proper classes, there was no checking of varibles before operations, data was overwritten in memory..... needless to say it crashed often and randomly.
    Most of the data was/is written directly to files and then read back when needed, and like you said : Using a file to basically simulate an array is just horrible. i've spent 8 months trying to sort it all out.

    The most annoying part is the almost complete lack of comments throughout the entire app.

    Maybe i'll have to start from scratch but i'm running out of time and this is just a very small part of the app.

    Thanks again dude

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Binary Tree Search
    By C++Newbie in forum C++ Programming
    Replies: 7
    Last Post: 04-05-2011, 01:17 AM
  2. Interpreter.c
    By moussa in forum C Programming
    Replies: 4
    Last Post: 05-28-2008, 05:59 PM
  3. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM
  4. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 09:33 AM
  5. BST/Red and Black Tree
    By ghettoman in forum C++ Programming
    Replies: 0
    Last Post: 10-24-2001, 10:45 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21