Subversion Repository Public Repository

Divide-Framework

This repository has no backups
This repository's network speed is throttled to 100KB/sec

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
#include "stdafx.h"

#include "Headers/QuadtreeNode.h"

#include "Managers/Headers/SceneManager.h"
#include "Platform/Video/Headers/GFXDevice.h"
#include "Platform/Video/Headers/IMPrimitive.h"
#include "Platform/Video/Headers/RenderStateBlock.h"
#include "Environment/Terrain/Headers/Terrain.h"
#include "Environment/Terrain/Headers/TerrainChunk.h"
#include "Core/Math/BoundingVolumes/Headers/BoundingBox.h"

namespace Divide {

QuadtreeNode::QuadtreeNode()
    : _terrainChunk(nullptr),
      _bbPrimitive(nullptr),
      _children(nullptr),
      _frustPlaneCache(-1)
{
    _targetChunkDimension = 0;
}

QuadtreeNode::~QuadtreeNode()
{
    MemoryManager::DELETE(_terrainChunk);
    MemoryManager::DELETE(_children);
}

void QuadtreeNode::Build(GFXDevice& context,
                         U8 depth,
                         const vec2<U32>& pos,
                         const vec2<U32>& HMsize,
                         U32 targetChunkDimension,
                         Terrain* const terrain,
                         U32& chunkCount)
{
    _targetChunkDimension = targetChunkDimension;
    U32 div = to_U32(std::pow(2.0f, to_F32(depth)));
    vec2<U32> nodesize = HMsize / (div);
    if (nodesize.x % 2 == 0) {
        nodesize.x++;
    }
    if (nodesize.y % 2 == 0) {
        nodesize.y++;
    }
    vec2<U32> newsize = nodesize / 2;

    if (std::max(newsize.x, newsize.y) <= _targetChunkDimension) {
        _terrainChunk = MemoryManager_NEW TerrainChunk(context, terrain, this);
        _terrainChunk->load(depth, pos, _targetChunkDimension, HMsize);
        chunkCount++;
    } else {
        // Create 4 children
        _children = MemoryManager_NEW QuadtreeChildren();

        QuadtreeChildren::QuadtreeNodes& childNodes = (*_children)();

        // Compute children bounding boxes
        const vec3<F32>& center = _boundingBox.getCenter();
        childNodes[to_base(ChildPosition::CHILD_NW)].setBoundingBox(BoundingBox(_boundingBox.getMin(), center));
        childNodes[to_base(ChildPosition::CHILD_NE)].setBoundingBox(BoundingBox(vec3<F32>(center.x, 0.0f, _boundingBox.getMin().z), vec3<F32>(_boundingBox.getMax().x, 0.0f, center.z)));
        childNodes[to_base(ChildPosition::CHILD_SW)].setBoundingBox(BoundingBox(vec3<F32>(_boundingBox.getMin().x, 0.0f, center.z), vec3<F32>(center.x, 0.0f, _boundingBox.getMax().z)));
        childNodes[to_base(ChildPosition::CHILD_SE)].setBoundingBox(BoundingBox(center, _boundingBox.getMax()));

        // Compute children positions
        vec2<U32> tNewHMpos[4];
        tNewHMpos[to_base(ChildPosition::CHILD_NW)] = pos + vec2<U32>(0, 0);
        tNewHMpos[to_base(ChildPosition::CHILD_NE)] = pos + vec2<U32>(newsize.x, 0);
        tNewHMpos[to_base(ChildPosition::CHILD_SW)] = pos + vec2<U32>(0, newsize.y);
        tNewHMpos[to_base(ChildPosition::CHILD_SE)] = pos + vec2<U32>(newsize.x, newsize.y);

        childNodes[to_base(ChildPosition::CHILD_NW)].Build(context, depth + 1, tNewHMpos[to_base(ChildPosition::CHILD_NW)], HMsize, _targetChunkDimension, terrain, chunkCount);
        childNodes[to_base(ChildPosition::CHILD_NE)].Build(context, depth + 1, tNewHMpos[to_base(ChildPosition::CHILD_NE)], HMsize, _targetChunkDimension, terrain, chunkCount);
        childNodes[to_base(ChildPosition::CHILD_SW)].Build(context, depth + 1, tNewHMpos[to_base(ChildPosition::CHILD_SW)], HMsize, _targetChunkDimension, terrain, chunkCount);
        childNodes[to_base(ChildPosition::CHILD_SE)].Build(context, depth + 1, tNewHMpos[to_base(ChildPosition::CHILD_SE)], HMsize, _targetChunkDimension, terrain, chunkCount);
    }
}

bool QuadtreeNode::computeBoundingBox() {
    if (_terrainChunk != nullptr) {
        _boundingBox.setMin(vec3<F32>(_boundingBox.getMin().x,
                                      _terrainChunk->getMinHeight(),
                                      _boundingBox.getMin().z));
        _boundingBox.setMax(vec3<F32>(_boundingBox.getMax().x,
                                      _terrainChunk->getMaxHeight(),
                                      _boundingBox.getMax().z));
    }

    if (!isALeaf()) {
        for (I8 i = 0; i < 4; i++) {
            QuadtreeNode& child = getChild(i);

            child.computeBoundingBox();

            if (_boundingBox.getMin().y >
                child._boundingBox.getMin().y) {
                _boundingBox.setMin(
                    vec3<F32>(_boundingBox.getMin().x,
                              child._boundingBox.getMin().y,
                              _boundingBox.getMin().z));
            }

            if (_boundingBox.getMax().y <
                child._boundingBox.getMax().y) {
                _boundingBox.setMax(
                    vec3<F32>(_boundingBox.getMax().x,
                              child._boundingBox.getMax().y,
                              _boundingBox.getMax().z));
            }
        }
    }

    _boundingSphere.fromBoundingBox(_boundingBox);
    return true;
}

U8 QuadtreeNode::getLoD(const vec3<F32>& eyePos) const {
    static const U32 TERRAIN_LOD0_SQ = Config::TERRAIN_LOD0 * Config::TERRAIN_LOD0;
    static const U32 TERRAIN_LOD1_SQ = Config::TERRAIN_LOD1 * Config::TERRAIN_LOD1;

    F32 cameraDistanceSQ = _boundingSphere.getCenter().distanceSquared(eyePos);

    return cameraDistanceSQ > TERRAIN_LOD0_SQ
                            ? cameraDistanceSQ > TERRAIN_LOD1_SQ ? 2 : 1
                            : 0;
}

void QuadtreeNode::sceneUpdate(const U64 deltaTime, SceneGraphNode& sgn, SceneState& sceneState) {
    if (isALeaf()) {
        ACKNOWLEDGE_UNUSED(deltaTime);
        ACKNOWLEDGE_UNUSED(sgn);
        ACKNOWLEDGE_UNUSED(sceneState);
    } else {
        getChild(ChildPosition::CHILD_NW).sceneUpdate(deltaTime, sgn, sceneState);
        getChild(ChildPosition::CHILD_NE).sceneUpdate(deltaTime, sgn, sceneState);
        getChild(ChildPosition::CHILD_SW).sceneUpdate(deltaTime, sgn, sceneState);
        getChild(ChildPosition::CHILD_SE).sceneUpdate(deltaTime, sgn, sceneState);
    }
}

bool QuadtreeNode::isInView(U32 options, const SceneRenderState& sceneRenderState) const {
    if (BitCompare(options, to_base(ChunkBit::CHUNK_BIT_TESTCHILDREN))) {
        const Camera& cam = *Camera::activeCamera();
        F32 boundingRadius = _boundingSphere.getRadius();
        const vec3<F32>& boundingCenter = _boundingSphere.getCenter();

        if (!BitCompare(options, to_base(ChunkBit::CHUNK_BIT_SHADOWMAP))) {
            const vec3<F32>& eye = cam.getEye();
            F32 visibilityDistance = sceneRenderState.generalVisibility() + boundingRadius;
            if (boundingCenter.distance(eye) > visibilityDistance) {
                if (_boundingBox.nearestDistanceFromPointSquared(eye) > std::min(visibilityDistance, cam.getZPlanes().y)) {
                    return false;
                }
            }
        }

        if (!_boundingBox.containsPoint(cam.getEye())) {

            const Frustum& frust = cam.getFrustum();
            switch (frust.ContainsSphere(boundingCenter, boundingRadius, _frustPlaneCache)) {
                case Frustum::FrustCollision::FRUSTUM_OUT:
                    return false;
                case Frustum::FrustCollision::FRUSTUM_IN:
                    options &= ~to_base(ChunkBit::CHUNK_BIT_TESTCHILDREN);
                    break;
                case Frustum::FrustCollision::FRUSTUM_INTERSECT: {
                    switch (frust.ContainsBoundingBox(_boundingBox, _frustPlaneCache)) {
                        case Frustum::FrustCollision::FRUSTUM_IN:
                            options &= ~to_base(ChunkBit::CHUNK_BIT_TESTCHILDREN);
                            break;
                        case Frustum::FrustCollision::FRUSTUM_OUT:
                            return false;
                    };  // inner switch
                };      // case Frustum::FrustCollision::FRUSTUM_INTERSECT
            };          // outer case
        }               // if
    }                   // ChunkBit::CHUNK_BIT_TESTCHILDREN option

    return true;
}

void QuadtreeNode::drawBBox(GFXDevice& context, RenderPackage& packageOut) {
    if (!_bbPrimitive) {
        _bbPrimitive = context.newIMP();
        _bbPrimitive->name("QuadtreeNodeBoundingBox");
        RenderStateBlock primitiveRenderState;
        PipelineDescriptor pipeDesc;
        pipeDesc._stateHash = primitiveRenderState.getHash();
        _bbPrimitive->pipeline(context.newPipeline(pipeDesc));
    }

    _bbPrimitive->fromBox(_boundingBox.getMin(),
                          _boundingBox.getMax(),
                          vec4<U8>(0, 128, 255, 255));

    packageOut.addCommandBuffer(_bbPrimitive->toCommandBuffer());

    if (!isALeaf()) {
        getChild(ChildPosition::CHILD_NW).drawBBox(context, packageOut);
        getChild(ChildPosition::CHILD_NE).drawBBox(context, packageOut);
        getChild(ChildPosition::CHILD_SW).drawBBox(context, packageOut);
        getChild(ChildPosition::CHILD_SE).drawBBox(context, packageOut);
    }
}
};

Commits for Divide-Framework/trunk/Source Code/Environment/Terrain/Quadtree/QuadtreeNode.cpp

Diff revisions: vs.
Revision Author Commited Message
949 Diff Diff IonutCava picture IonutCava Thu 19 Oct, 2017 21:48:37 +0000

[Ionut]
- More command buffer refactoring

943 Diff Diff IonutCava picture IonutCava Tue 12 Sep, 2017 11:38:52 +0000

[IonutCava]
- Rework ThreadPool/Task system for clearer parent<->child relationship between tasks
— Disable Prio pool since it doesn’t work properly with the newest boost libraries
— Modify the C++11 threadpool to remove the boost dependency
- Reduce memory usage by allocating command buffers on use instead of on creation

933 Diff Diff IonutCava picture IonutCava Tue 15 Aug, 2017 00:02:05 +0000

[Ionut]
- CommandBuffer Part 2/3: code compiles and splash screen renders and application doesn’t crash (still has drawing issues)

929 Diff Diff IonutCava picture IonutCava Sat 12 Aug, 2017 17:34:44 +0000

[Ionut]
- More work on finishing up new PushConstant / Command buffer rendering system:
— Everything compiles and runs but with graphical and performance issues

893 Diff Diff IonutCava picture IonutCava Sun 18 Jun, 2017 17:33:07 +0000

[Ionut]
- Initial implementation of a PipelineStateObject (holds shader program, rasterizer state, etc)
- Rework PCH implementation a bit because VS2017 no longer has a /ZM option

890 Diff Diff IonutCava picture IonutCava Sun 14 May, 2017 20:54:59 +0000

[Ionut]
- Add pre-compiled header support
- Initial code for per-stage tessellation computation

881 Diff Diff IonutCava picture IonutCava Tue 21 Mar, 2017 22:07:37 +0000

[IonutCava]
- Multi draw command bug fix: drawCount > 1 should properly register all commands in the command buffer
- More tessellated terrain updates and fixes (still Work In Progress)

880 Diff Diff IonutCava picture IonutCava Mon 20 Mar, 2017 17:27:13 +0000

[IonutCava]
- New tessellated terrain system based on this: http://victorbush.com/2015/01/tessellated-terrain/
— Work in progress: hardcoded values, new code is in Test namespace
- Split terrain geometry in two:
— tessellated rendering data
— physics verts + indices (used for collisions, vegetation, etc)
- Old Chunk system is used only for culling objects and speeding up collision detection

874 Diff Diff IonutCava picture IonutCava Mon 13 Mar, 2017 17:29:45 +0000

[IonutCava]
- Fix boundingbox skewing bug.
- Optimise frustum collision checks by adding a plane-cache system.
— ToDo: solve mutable status of _frustPlaneCache
— ToDo: TRIPLE check results to avoid false-positives
- Speedup terrain by not stack-allocating QuadtreeNodes in a QuadtreeChildren container instead of new-ing each one of them.

872 IonutCava picture IonutCava Mon 06 Mar, 2017 23:23:20 +0000

[IonutCava]
- Optimise static casts