### Author Topic: the swept  (Read 9843 times)

#### theFALCO

• byte
• Posts: 39
##### the swept
« on: December 17, 2006, 09:19:00 pm »
what exactly is this swept algorithm? is it like I have an object and if it collides with a ramp it moves up the ramp instead of getting blocked? if yes, how do I set the max hight?

#### EgonOlsen

• Posts: 12035
##### the swept
« Reply #1 on: December 18, 2006, 01:51:29 pm »
Yes, basically. It's called "swept", because it sweeps across the scene. Not like the sphere-implementation, which just evaluates the final position. For every obstacle, a sliding plane is calculated as the tangent plane to the ellipsoid in the point of contact with the obstacle. So yes, it will move up that ramp. Anything else (how far...etc) is application logic and has to be done in your code somehow.

#### theFALCO

• byte
• Posts: 39
##### the swept
« Reply #2 on: December 18, 2006, 07:22:55 pm »
I'm interested in the 'somehow' part. What I mean is that I have created an object and a terrain. In the loop I call the checkForCollisionEllipsoid() (terrain set to COLLISION_CHECK_OTHERS and the model a.k.a. cube is COLLISION_CHECK_SELF) here is the code:
Code: [Select]
`/* in the initialization */        float[] bf = cube.getMesh().getBoundingBox();        Csiz.x = Math.abs(bf[0])+Math.abs(bf[1]);        Csiz.y = Math.abs(bf[2])+Math.abs(bf[3]);        Csiz.z = Math.abs(bf[4])+Math.abs(bf[5]);/* the following is in the main loop */        SimpleVector grav = new SimpleVector(0, GRAVITY, 0);        grav = cube.checkForCollisionEllipsoid(grav, Csiz, 1);        grav.x=0;        grav.z=0;        cube.translate(grav);        t=1;        if(cube.wasTargetOfLastCollision()) {            inAir=false;        }        if(right) {            cube.rotateY(0.01f);        }        if(left) {            cube.rotateY(-0.01f);        }        if(up) {            cube.rotateAxis(cube.getXAxis(), -0.01f);        }        if(down) {            cube.rotateAxis(cube.getXAxis(), 0.01f);        }        if(forward) {            t=2;            SimpleVector fax = cube.getZAxis();            fax.scalarMul(1f);            fax=cube.checkForCollisionEllipsoid(fax, Csiz, 1);            cube.translate(fax);        }`

As you can see not only my model sticks in the ground to knees but also it can't climb even the smallest ramp. On this screenshot it is blocked.

However I don't think it's really a swept-related problem. I have created a simple map which is flat and cube gets stuck even there .

I'm using here the trrain from car example and bill model somewhere from this forum (btw. thanks for it ).

#### EgonOlsen

• Posts: 12035
##### the swept
« Reply #3 on: December 18, 2006, 07:35:35 pm »
First of all, your ellipsoid calculation isn't correct. If, for example, xMin is -4 and xMax is 4, your formula gets you a x-radius of 8, where it actually should be 4. Ellipsoid collision detection is not suitable to push you out of a collision, so maybe you are already colliding with the ground (given that large radius) when doing the gravity check. Make sure that the ellipsoid is collision free before starting.
Second, a recursion depth of 1 will never let you slide, because you'll stop at the first point of contact. Values like 4 to 6 are usually reasonable.

#### theFALCO

• byte
• Posts: 39
##### the swept
« Reply #4 on: December 18, 2006, 07:55:02 pm »
Quote from: "EgonOlsen"
Make sure that the ellipsoid is collision free before starting

It isn't

When I change to Csiz.x/y/z = (blahblah) / 2; the model gets stuck even further to the ground.

Increasing 1 to 6 doesn't help.

When I change the cube from new Object3D(400) to Primitives.getCube(1) it works perfectly with no blocking but when I change to getCube(10) it gets blocked...

#### EgonOlsen

• Posts: 12035
##### the swept
« Reply #5 on: December 18, 2006, 08:01:02 pm »
Well, then make sure that it is collision free. The algorithm simply can't move you out of a collision, it can just prevent a collision to happen. So if you start collision free, you should never run into one. The problem is: You can't calculate a sliding plane that pushs you out of the collision if you are already in one.
You may try to do a single call to the spherical collision detection with rMax(+0.1 to be sure) (of the ellipsoid) as radius of the sphere and no translation. The resulting translation may push you out of this initial collision.

#### theFALCO

• byte
• Posts: 39
##### the swept
« Reply #6 on: December 18, 2006, 08:19:49 pm »
it is collision free (it is spawned to fall down at the beginning)

what I have noticed is the bigger it is the less the swept is working...

#### EgonOlsen

• Posts: 12035
##### the swept
« Reply #7 on: December 18, 2006, 08:25:21 pm »
Try to increase Config.collideOffset. Maybe the collision isn't recognized correctly because the vertices are too far away. If that doesn't help, please post a simple test case.

#### theFALCO

• byte
• Posts: 39
##### the swept
« Reply #8 on: December 18, 2006, 08:31:00 pm »
Config.collideOffset = 10000;

still nothing
what's a test case?

#### EgonOlsen

• Posts: 12035
##### the swept
« Reply #9 on: December 18, 2006, 08:40:07 pm »
Some code that shows the problem that i can take, compile and execute to see what's actually wrong here.

#### theFALCO

• byte
• Posts: 39
##### the swept
« Reply #10 on: December 18, 2006, 08:51:24 pm »
actually it's everything :roll:
Code: [Select]
`import java.io.*;import java.awt.*;import java.awt.event.*;import java.awt.image.*;import com.threed.jpct.*;import com.threed.jpct.util.*;class Cube {    /* Engine Specific */    private final static int SWITCH_RENDERER=35;    private boolean fullscreen=false;    private boolean openGL=true;    private boolean wireframe=false;    private FrameBuffer buffer=null;    private World theWorld=null;    private TextureManager texMan=null;    private Camera camera=null;    private int width=640;    private int height=480;    private Frame frame=null;    private Graphics gFrame=null;    private BufferStrategy bufferStrategy=null;    private GraphicsDevice device=null;    private int titleBarHeight=0;    private int leftBorderWidth=0;    private int switchMode=0;    private int fps;    private int lastFps;    private long totalFps;    private int pps;    private int lastPps;    private boolean isIdle=false;    private boolean exit=false;    private boolean left=false;    private boolean right=false;    private boolean up=false;    private boolean down=false;    private boolean forward=false;    private boolean back=false;    private boolean jump=false;    private boolean inAir=false;    private boolean fire=false;    private int fireCount=3;    private float GRAVITY=1f;    private int theIlluminator;    private float camAlt=125f;    private float camDist=150f;    private boolean camUp=false;    private boolean camDown=false;    private boolean camIn=false;    private boolean camOut=false;    private float speed=0;    private int t=0;    private float z=0f;    private KeyMapper keyMapper=null;    private Object3D cube = /*Primitives.getCube(10);*/new Object3D(400);    private Object3D terrain = new Object3D(400);    private SimpleVector Csiz = new SimpleVector();    private Cube(String[] args) {        /* init stuff */        char c=File.separatorChar;        Config.glFullscreen=false;        Config.glMipmap=true;        Config.glColorDepth=16;        Config.maxPolysVisible=10000;        /* process commandline arguments */        for(int i=0;i<args.length;i++) {            if(args[i].equals("fullscreen")) {                Config.glFullscreen=true;            }            if(args[i].equals("noGL")) {                openGL=false;            }        }        isIdle=false;        switchMode=0;        totalFps=0;        fps=0;        lastFps=0;        theWorld=new World();        //Lights!        Config.fadeoutLight=false;        theWorld.getLights().setOverbrightLighting(Lights.OVERBRIGHT_LIGHTING_DISABLED);        theWorld.getLights().setRGBScale(Lights.RGB_SCALE_2X);        theWorld.setAmbientLight(25, 30, 30);        theWorld.addLight(new SimpleVector(0, -150, 0), 10, 10, 10);        theWorld.addLight(new SimpleVector(-1000, -1000, 1000), 5, 5, 5);        theWorld.addLight(new SimpleVector(1000, -1000, -1000), 5, 5, 5);        theIlluminator=theWorld.addLight(new SimpleVector(1000, -1000, -1000), 255, 0, 0);        theWorld.setLightDiscardDistance(theIlluminator, 20);        //Fog!        theWorld.setFogging(World.FOGGING_ENABLED);        theWorld.setFogParameters(5000, 0, 0, 0);        Config.farPlane=5000;        //Textures!        texMan=TextureManager.getInstance();        texMan.addTexture("teks", new Texture("textures"+c+"ql0.jpg"));        texMan.addTexture("rocks", new Texture("textures"+c+"rocks.jpg"));        //World!        terrain=Loader.load3DS("models"+c+"terascene.3ds", 1000)[0];        terrain.setOrigin(new SimpleVector(0, 0, 0));        terrain.rotateX((float)-Math.PI/2f);        terrain.setTexture("rocks");        terrain.createTriangleStrips(2);        OcTree oc = new OcTree(terrain, 50, OcTree.MODE_OPTIMIZED);        terrain.setOcTree(oc);        oc.setCollisionUse(OcTree.COLLISION_USE);        Config.collideOffset=250;        terrain.setCollisionMode(Object3D.COLLISION_CHECK_OTHERS);        terrain.setCollisionOptimization(Object3D.COLLISION_DETECTION_OPTIMIZED);        //add listener        theWorld.addObject(terrain);        //theCUBE!        cube=Loader.loadMD2("models"+c+"bill"+c+"tris.MD2", 1f);        cube.rotateY((float)-Math.PI/2f);        cube.rotateMesh();        cube.setRotationMatrix(new Matrix());        texMan.addTexture("suit", new Texture("models"+c+"bill"+c+"billywork.jpg"));        //cube.setBaseTexture("suit");        cube.setTexture("suit");        cube.setCollisionMode(Object3D.COLLISION_CHECK_SELF);        //cube.setCollisionOptimization(Object3D.COLLISION_DETECTION_OPTIMIZED);        cube.setTranslationMatrix(new Matrix());        theWorld.addObject(cube);        float[] bf = cube.getMesh().getBoundingBox();        Csiz.x = (Math.abs(bf[0])+Math.abs(bf[1]))/2f;        Csiz.y = (Math.abs(bf[2])+Math.abs(bf[3]))/2f;        Csiz.z = (Math.abs(bf[4])+Math.abs(bf[5]))/2f;        Logger.log("============================", Logger.MESSAGE);        for(int i=0;i<6;i++) {            Logger.log(String.valueOf(bf[i]), Logger.MESSAGE);        }        Logger.log("============================", Logger.MESSAGE);        Logger.log(String.valueOf(Csiz.x), Logger.MESSAGE);        Logger.log(String.valueOf(Csiz.y), Logger.MESSAGE);        Logger.log(String.valueOf(Csiz.z), Logger.MESSAGE);        Logger.log("============================", Logger.MESSAGE);        //Camera!        camera=theWorld.getCamera();        camera.setPosition(0, 0, 10);        camera.lookAt(cube.getTransformedCenter());        theWorld.buildAllObjects();        Config.tuneForOutdoor();        initializeFrame();        gameLoop();    }    public static void main(String[] args) {        /* main stuff */        new Cube(args);    }    private void initializeFrame() {        if (Config.glFullscreen) {            GraphicsEnvironment env=GraphicsEnvironment.getLocalGraphicsEnvironment();            device=env.getDefaultScreenDevice();            GraphicsConfiguration gc=device.getDefaultConfiguration();            frame=new Frame(gc);            frame.setUndecorated(true);            frame.setIgnoreRepaint(true);            device.setFullScreenWindow(frame);            if (device.isDisplayChangeSupported()) {                device.setDisplayMode(new DisplayMode(width, height, 32, 0));            }            frame.createBufferStrategy(2);            bufferStrategy=frame.getBufferStrategy();            Graphics g=bufferStrategy.getDrawGraphics();            bufferStrategy.show();            g.dispose();        } else {            frame=new Frame("jPCT "+Config.getVersion());            frame.pack();            Insets insets = frame.getInsets();            titleBarHeight=insets.top;            leftBorderWidth=insets.left;            frame.setSize(width+leftBorderWidth+insets.right, height+titleBarHeight+insets.bottom);            frame.setResizable(false);            frame.show();            gFrame=frame.getGraphics();        }        frame.addWindowListener(new WindowEvents());        keyMapper=new KeyMapper(frame);    }    private void moveCube() {        SimpleVector grav = new SimpleVector(0, GRAVITY, 0);        grav = cube.checkForCollisionEllipsoid(grav, Csiz, 6);        grav.x=0;        grav.z=0;        cube.translate(grav);        t=1;        if(cube.wasTargetOfLastCollision()) {            inAir=false;        }        if(right) {            cube.rotateY(0.01f);        }        if(left) {            cube.rotateY(-0.01f);        }        if(up) {            cube.rotateAxis(cube.getXAxis(), -0.01f);        }        if(down) {            cube.rotateAxis(cube.getXAxis(), 0.01f);        }        if(forward) {            t=2;            SimpleVector fax = cube.getZAxis();            fax.scalarMul(1f);            fax=cube.checkForCollisionEllipsoid(fax, Csiz, 6);            cube.translate(fax);        }        if(back) {            SimpleVector bax = cube.getZAxis();            bax.scalarMul(-0.5f);            bax=cube.checkForCollisionEllipsoid(bax, Csiz, 25);            cube.translate(bax);        }        if(jump) {            if(!inAir) {                SimpleVector jax = cube.getZAxis();                jax.scalarMul(-1f);                jax.add(new SimpleVector(0, -5, 0));                jax.x=0;                jax.z=0;                jax=cube.checkForCollisionEllipsoid(jax, Csiz, 25);                cube.translate(jax);                //inAir=true;            }        }        if(camUp) {            camAlt+=0.5f;        }        if(camDown) {            camAlt-=0.5f;        }        if(camIn) {            camDist-=0.5f;        }        if(camOut) {            camDist+=0.5f;        }        // Anim        if(z>1f) {            z=0f;        }        cube.animate(z, t);        z+=0.001f;    }    private void display() {        if (buffer.usesRenderer(IRenderer.RENDERER_SOFTWARE)) {            if (Config.glFullscreen) {                Graphics g=bufferStrategy.getDrawGraphics();                g.drawImage(buffer.getOutputBuffer(), 0, 0, null);                bufferStrategy.show();                g.dispose();            } else {                buffer.display(gFrame, leftBorderWidth, titleBarHeight);            }        } else {            buffer.displayGLOnly();        }    }    private void gameLoop() {        World.setDefaultThread(Thread.currentThread());        buffer=new FrameBuffer(width, height, FrameBuffer.SAMPLINGMODE_NORMAL);        buffer.enableRenderer(IRenderer.RENDERER_SOFTWARE);        if(openGL) {            frame.hide();            keyMapper.destroy();            buffer.enableRenderer(IRenderer.RENDERER_OPENGL, IRenderer.MODE_OPENGL);            buffer.disableRenderer(IRenderer.RENDERER_SOFTWARE);            keyMapper=new KeyMapper();        }        buffer.setBoundingBoxMode(FrameBuffer.BOUNDINGBOX_NOT_USED);        buffer.optimizeBufferAccess();        Timer timer = new Timer(25);        timer.start();        while(!exit) {            if(!isIdle) {                poll();                buffer.clear();                theWorld.renderScene(buffer);                theWorld.draw(buffer);                buffer.update();                moveCube();                SimpleVector ilpos=cube.getTransformedCenter();                theWorld.setLightPosition(theIlluminator, ilpos);                camera.setPosition(cube.getTransformedCenter());                camera.align(cube);                camera.moveCamera(Camera.CAMERA_MOVEOUT, camDist);                camera.moveCamera(Camera.CAMERA_MOVEUP, camAlt);                camera.lookAt(cube.getTransformedCenter());                display();                Thread.yield();            }        }        if (openGL) {            buffer.disableRenderer(IRenderer.RENDERER_OPENGL);        } else {            if (fullscreen) {                device.setFullScreenWindow(null);            }        }        System.exit(0);    }    private void keyAffected(KeyState state) {        int code = state.getKeyCode();        boolean event = state.getState();        switch(code) {            case(KeyEvent.VK_ESCAPE): {                exit=true;                break;            }            case(KeyEvent.VK_RIGHT): {                right=event;                break;            }            case(KeyEvent.VK_LEFT): {                left=event;                break;            }            case(KeyEvent.VK_UP): {                forward=event;                break;            }            case(KeyEvent.VK_DOWN): {                back=event;                break;            }            case(KeyEvent.VK_SPACE): {                jump=event;                break;            }            case(KeyEvent.VK_NUMPAD4): {                camUp=event;                break;            }            case(KeyEvent.VK_NUMPAD1): {                camDown=event;                break;            }            case(KeyEvent.VK_NUMPAD5): {                camIn=event;                break;            }            case(KeyEvent.VK_NUMPAD2): {                camOut=event;                break;            }            case(KeyEvent.VK_INSERT): {                t++;                if(t>17) {                    t=0;                }            }        }    }    private void poll() {        KeyState state = null;        do {            state=keyMapper.poll();            if(state != KeyState.NONE) {                keyAffected(state);            }        } while (state != KeyState.NONE);    }    private class WindowEvents extends WindowAdapter {        public void windowIconified(WindowEvent e) {            isIdle=true;        }        public void windowDeiconified(WindowEvent e) {            isIdle=false;        }    }    private class Timer {        private long ticks=0;        private long granularity=0;        public Timer(int granularity) {            this.granularity=granularity;        }        public void start() {            ticks=System.currentTimeMillis();        }        public void reset() {            start();        }        public long getElapsedTicks() {            long cur=System.currentTimeMillis();            long l=cur-ticks;            if (l>=granularity) {                ticks=cur-(l%granularity);                return l/granularity;            }            return 0;        }    }}`

you'll also need a model (cause the cube isn't sticking in the ground, it's just getting blocked if too big, for instance 10)

#### EgonOlsen

• Posts: 12035
##### the swept
« Reply #11 on: December 18, 2006, 10:20:58 pm »
There are a couple of issues with your approach. What you are trying to do is terrain following. Ellipsoid collision detection isn't exactly the best approach to do this (that's why the car-example doesn't use it).
The sliding planes will cause your moving entity to leave the straight line it's supposed to travel, so when climbing steep edges, you'll most likely move around somehow but not in a straight line.
Doing gravity with it can be troublesome too. The sliding plane for "forward" can be totally different from that for "down" so the result looks strange if it moves at all. I strongly suggest to consider an approach like the car example was using it, if terrain following really it what you are planning to do. If the terrain acts as a placeholder for something else (like an indoor level), this may not be an issue later on.
Anyway, it wasn't moving at all, so...: If you want to do it that way, combine gravity and translation to one SimpleVector which results in one sliding plane. This avoids the problem that one translation says "hoh" while the other says "huh" and the result is "hohuh"...which may look strange.
I've modified the moveCube-method to reflect this. This may not be a  100% solution. I'll leave it up to you to come up with a better one:

Code: [Select]
`private void moveCube() {        t=1;        Config.collideEllipsoidThreshold=0.00005f;        terrain.setCollisionOptimization(Object3D.COLLISION_DETECTION_OPTIMIZED);        if(cube.wasTargetOfLastCollision()) {            inAir=false;        }        if(right) {            cube.rotateY(0.01f);        }        if(left) {            cube.rotateY(-0.01f);        }        if(up) {            cube.rotateAxis(cube.getXAxis(), -0.01f);        }        if(down) {            cube.rotateAxis(cube.getXAxis(), 0.01f);        }        boolean moved=false;        if(forward) {            t=2;            SimpleVector fax = cube.getZAxis();            fax.y+=1;            fax=fax.normalize();            fax.scalarMul(1f);            fax=cube.checkForCollisionEllipsoid(fax, Csiz, 25);            cube.translate(fax);            moved=true;        }        if(back) {            SimpleVector bax = cube.getZAxis();            bax.scalarMul(-0.5f);            bax.y+=1;            bax=bax.normalize();            bax=cube.checkForCollisionEllipsoid(bax, Csiz, 25);            cube.translate(bax);            moved=true;        }        if(jump) {            if(!inAir) {                SimpleVector jax = cube.getZAxis();                jax.scalarMul(-1f);                jax.add(new SimpleVector(0, -5, 0));                jax=cube.checkForCollisionEllipsoid(jax, Csiz, 6);                cube.translate(jax);                moved=true;            }        }                if (!moved) {           SimpleVector grav=new SimpleVector(0,GRAVITY,0);           grav=cube.checkForCollisionEllipsoid(grav, Csiz, 1);           cube.translate(grav);        }                if(camUp) {            camAlt+=0.5f;        }        if(camDown) {            camAlt-=0.5f;        }        if(camIn) {            camDist-=0.5f;        }        if(camOut) {            camDist+=0.5f;        }        // Anim        if(z>1f) {            z=0f;        }        cube.animate(z, t);        z+=0.001f;    }`

Another setting you've to adjust is Config.collideEllipsoidThreshold. I've set it to 0.00005f; which seemed reasonable. A value too high can block the recursion too early while a too low one can cause problems due to rounding errors in the calculation. A good value depends on the scene and the ellipsoid's size. It's hard to predict what works best...at least i've never found a good way to get a reasonable value without trying.

About the model sticking in the ground: An objects center as calculated by jPCT is the average of its vertices. On a human body, this tends to be located somewhere in the chest, because more vertices define the head and the body than the legs. So either increase the size of the ellipsoid (which will make it extend above the head) or adjust the center (try (0,0,0) instead).

Hope this helps.

#### theFALCO

• byte
• Posts: 39
##### the swept
« Reply #12 on: December 31, 2006, 07:12:57 pm »
Could you provide any small (only the essentials - the less, the better) example of a working swept? A simple "cube moves up the ramp", please?

#### EgonOlsen

• Posts: 12035
##### the swept
« Reply #13 on: January 01, 2007, 02:35:31 am »
Yes, but it'll take some time. Maybe this thursday, if i find the time. The fps-example uses this algoritm too. Maybe it helps until then.

#### theFALCO

• byte
• Posts: 39
##### the swept
« Reply #14 on: January 01, 2007, 12:21:41 pm »
the FPS example uses cameraCheckCollisionEllipsoid(), maybe it differs

maybe it's because I use cube.checkForCollisionEllipsoid, not theWorld.check..., maybe... I don't know, maybe I have to make my own SWEPT, but I don't know how... :?