Thread: "subtractive geometry"?

  1. #1
    The Right Honourable psychopath's Avatar
    Join Date
    Mar 2004
    Location
    Where circles begin.
    Posts
    1,071

    "subtractive geometry"?

    how can i make geometry, that when it intersects other geometry, makes the intersection area not rendered?

    what i'm trying to say is better explained in the following image,
    the red is solid geometry, the blue is subtractive geometry, and the grey with blue lines is the intersection point that is not rendered.
    M.Eng Computer Engineering Candidate
    B.Sc Computer Science

    Robotics and graphics enthusiast.

  2. #2
    Registered User
    Join Date
    Mar 2003
    Posts
    580
    What are the constraints for the geometry?

    If this is 3D with arbitrary geometry, the math for something like that is beyond most people.

  3. #3
    The Right Honourable psychopath's Avatar
    Join Date
    Mar 2004
    Location
    Where circles begin.
    Posts
    1,071
    yup...3d....i should also add that i'm using OpenGL

    -psychopath
    M.Eng Computer Engineering Candidate
    B.Sc Computer Science

    Robotics and graphics enthusiast.

  4. #4
    Registered User
    Join Date
    Mar 2003
    Posts
    580
    Hmm, well, I would like to encourage you to be able to do this, but I think that the math for doing this in 3D, with *arbitrary geometry* might be a bit more complex than even college level students to be able to do, and evidently you are 13.

    This is along the lines of something called 'constructive solid geometry', aka CSG for short. Although not exactly the same, CSG is a process that most map compilers use to be able to combine geometry into simpler geometry...for example if you placed to cubes right next to each other it would turn them into a single large rectangle (this means that there is less to send down the rendering pipeline later, as there are less repeating vertices). This is pertinent because it involves finding where geometry touches or intersects.

    So, are you willing to put some constraints on the type of geometry you are willing to use? For example, walls can only be perpendicular, or 45 degrees to each other (or some other specific angle)...something along those lines.

    Then, it makes the problem more feasible to solve.

    EDIT:
    If the geometry only ever looks simple, as it does in that picture you posted, then this is a pretty easy problem to solve, but you mentioned that you want this in full 3D, and it seems like you wanted it with arbitrary geometry (that's why I said what I said above).

  5. #5
    Registered User VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,607
    This can be done as you render your object. It's no different than having different levels of detail for terrain. At the detail border you must take away vertices. Instead of actually dumping the vertex, you simply weld two vertices together. So where you once had a vertex you now place that vertex one left or one right of it.

    You could use a D3DXSPMESH instead of a normal buffer. This interface already supports dynamic alterations to the mesh. However you will still have to tweak it a bit to accomplish what you want.

    The math for this is not complex at all, it's just a matter of indexing into vertex arrays and altering indexes temporarily.

  6. #6
    The Right Honourable psychopath's Avatar
    Join Date
    Mar 2004
    Location
    Where circles begin.
    Posts
    1,071
    ok thanks.
    after reading over both your replys and thinking everything over, i think i can probably get it to work.

    example:
    say i have a wall, and i want to cut a door shape into it:

    psuedo code:
    if (subtractive geometry intersects with solid geometry)
    {
    delete solid geometry();
    draw solid gemetry with ends being the end of the cut geometry and the other end where the end of the gemetry present previously was();
    do basicly the same thing as step two, only for what may be left on top of the cut geometry();
    }

    pic (red=solid, blue=cut/not rendered):
    M.Eng Computer Engineering Candidate
    B.Sc Computer Science

    Robotics and graphics enthusiast.

  7. #7
    Registered User
    Join Date
    Mar 2003
    Posts
    580
    If your geometry is only ever going to be as simple as in the pictures, then Bubba is correct in saying that the math is easy, and that it's as simple as moving vertices...as Bubba said you only need to move vertices to the right or left (meaning, the blue subtractive geometry gets its X component of the endpoint vertices set equal to the value of the inner walls of the red part).

    Otherwise if it is anymore complex you are dealing with 3D planes, convex volumes (convex is one of the constraints that are in 3D editors...I mentioned putting constraints on YOUR geometry, and convex is one of them...aka manifold...I can explain better if you want), and a vast world of complex algorithms that deal with 'polygon soup'.

  8. #8
    Crazy Fool Perspective's Avatar
    Join Date
    Jan 2003
    Location
    Canada
    Posts
    2,640
    ray trace the scene. if a ray intersects the the "subtractive" piece followed by the other geometry dont render it (colour that pixel black/background colour) otherwise, render as usual.

  9. #9
    Registered User
    Join Date
    Mar 2003
    Posts
    580
    Way to remain basic, lets introduce ray tracing to the 13 year old amateur coder.

    Next, why don't we start talking about how to numerically approximate the pressure difference and torque arm caused by exhaust shot out from the side of a basllistic missle that flies at 6,000 mph

    and if you do want to take Perspective's advice, you don't need to write a real 'ray tracer' so to speak...look into the stencil buffer. It is functionality which does sort of do ray tracing, in the sense that it can update the depth buffer of a rendered object based on z distances...but it still isn't real ray tracing. However, this is not good because it implies that you are doing this in real time. It is better to pre compile all of the vertices and then render the final product, although if you are using simple data the speed hit is trivial.
    Last edited by Darkness; 10-11-2004 at 11:59 AM.

  10. #10
    Registered User VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,607
    I would not recommend using the stencil buffer or the depth buffer for ray casting into 3D space. There are equations for ray to triangle, ray to bounding volume intersections that are much easier. Essentially you fire off 2 or more rays and see what they hit. More rays should only be done on big rigs as this slows down the code a lot.

  11. #11
    Registered User
    Join Date
    Mar 2003
    Posts
    580
    Quote Originally Posted by Bubba
    I would not recommend using the stencil buffer or the depth buffer for ray casting into 3D space. There are equations for ray to triangle, ray to bounding volume intersections that are much easier. Essentially you fire off 2 or more rays and see what they hit. More rays should only be done on big rigs as this slows down the code a lot.
    I do not condone using the stencil buffer OR ray tracing/casting for this trivial problem.

    But I must add, that the 'ray to triangle' and 'ray to bounding volume' are not only VERY complex because you must implement it from a VERY FUNDAMENTAL level but it's much slower to execute than rendering a triangle (which is all that the stencil buffer needs to do in order to do the depth compares).

    To get a ray to triangle intersection to work, you must either inflate the data using up a lot of memory to represent 3 inward pointing planes, OR you must make at least 3 sqrt and 3 acos calls to sum angles (in accordance to the algorithms I know of in order to do this).

    The other less expensive ray to bounding volume algorithms are just plain complex, such as the ray to brush algorithm, and using the stencil buffer would have been easier.

    But, as I said, both stencil buffer and ray casting/ray tracing are not appropriate for this problem.

    So psycopath, how are things actually coming? I've seem to have stolen this thread from you

  12. #12
    The Right Honourable psychopath's Avatar
    Join Date
    Mar 2004
    Location
    Where circles begin.
    Posts
    1,071
    ugh....guess i'll stick to basics for now, but thanks anyway

    >>So psycopath, how are things actually coming? I've seem to have stolen this thread from you<<
    not at all...but anyway, things are going pretty good...so far i have
    -first person camera
    -Texture Mapping (with mip-mapping
    -Multi-Texturing
    -Light-Mapping
    -Blending/Trasparency
    -SkyBox
    -Distance Fogging
    -Dynamic Lighting
    ..for the GameEngine/Game Creation program...the real problem lately has been "plugging" these features into the GUI of the actual program...but at least the features are there....much more to go, as there still arn't any gameplay features yet
    Anyway..theres more info on my site (www.psychopathproductions.tk)
    M.Eng Computer Engineering Candidate
    B.Sc Computer Science

    Robotics and graphics enthusiast.

  13. #13
    Registered User VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,607
    Every game on the market casts rays in one form or another. You have to in order to find out bullet paths, etc. Also games cast rays towards the sun in order to find out whether or not they must render a lense flare or not. Casting rays is not that hard and it does not require all that.

    But what you really want to do is portal rendering. Portal rendering is essentially what the new DOOM3 uses to render complex scenes with multiple exits in rooms. It also uses BSP/Portal rendering but I'll explain the portal rendering to you here.

    First you must create a scene graph. The graph determine what rooms are connected.

    Here is what you do. Each portal is a doorway or a bounding volume. Basically they are polygons that you will project into screen space to see if they overlap another volume or not. If they do, you render its associated geometry. If they dont, you don't render and you stop following the node.

    Step 1:
    In my example, bedroom 1 is where the camera is. Ok, so we know that all of bedroom 1's geometry must be rendered. So we render it and then we use it's portal polygon (or the poly that represents the doorway as the bounding volume or clipping volume for the next render.

    Step 2:
    When we leave the bedroom we are at hallway point 1. We project the hallway's bounding volume's against our bounding volume for the current room, which is the doorway for our room. Does the hallway's bounding volume overlap ours? Yes, it does so we render it and clip the geometry to our bounding volume - or the doorway to our room.

    Step 3:
    Now we have two paths. We can go to the hallway point 2 or bedroom 3. Performing a depth first traversal, we go to bedroom 3 and 'push' hallway point 2 onto our stack.

    Step 4:
    Now check bedroom 3's bounding volume against our bounding volume or portal - our doorway. Does it overlap? Yes. So we render all of bedroom 3 and clip it to hallway point 1's bounding volume or portal - essentially the doorway into bedroom 3.

    Step 5:
    There are no more node's for bedroom 3. We are done with this branch.

    Step 6:
    We pop hallway point 2 off of our stack and test. Does hallway point 2's bounding volume overlap ours?? No. Hallway point 2 will never be visible from our current location and thus none of it's nodes will be either. The scene is done.


    This is just one example of a portal renderer. This is the main visiblility determination algorithm. Then when a room passes, you use the BSP algorithm to effectively render it's geometry. Using both of these combinations will result in extremely fast renders, and extremely accurate rendering.

    I hope I explained it well enough.
    Last edited by VirtualAce; 10-12-2004 at 01:51 PM.

  14. #14
    Registered User VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,607
    Ray to triangle does not require 3 sqrts() or 3 arccos(). It only requires dot product.

    D3DXVec3Dot().

  15. #15
    Registered User
    Join Date
    Mar 2003
    Posts
    580
    Portal renderers aren't really the best unless you absolutely need strict culling. The reason is, a portal engine can only accept innately 'closed off regions' such as indoor environments. One of the constraints of geometry is that a region can only have portals as holes in its bounding volume. This doesn't work fast for outdoor environments, or even open-ended indoor environments.

    And also, the original poster is only looking into a 'CSG subtract' operation.

    And you are wrong about the ray to triangle only needing a dotproduct. If the 3 inward pointing planes are not stored, then you must calculate where the ray intersects the triangle plane, create vectors from the plane intersection to each vertex, and calculate the angles between each of these vectors which requires 3 sqrts and 3 acos calls, and must be approximately equal to 2PI radians if the ray intersects the triangle.

    Otherwise you have 3 planes which point inward and in THAT case yes you only need dotproduct. You have to weigh speed versus memory because these 3 planes

    a) will take up a lot of space, even for simple geometry
    b) cannot be compressed easily in any sort of scheme, because you cannot assume that adjacent triangles are always coplanar (often not)
    Last edited by Darkness; 10-12-2004 at 06:53 PM.
    See you in 13

Popular pages Recent additions subscribe to a feed